[Algorithm] 6월23일 알고리즘 연습 - 에이젠

 

Lv. 2 단체사진 찍기

참고한 풀이

 

class Solution {
    private int answer = 0;
    private String[] friends = {"A", "C", "F", "J", "M", "N", "R", "T"};

    public int solution(int n, String[] data) {
        boolean[] isVisited = new boolean[8];
        dfs("", isVisited, data);
        System.out.println(answer);
        return answer;
    }

    private void dfs(String names, boolean[] isVisited, String[] datas) {
        if (names.length() == 7) {
            if (check(names, datas)) { // 조건만족 체크
                answer++;
            }
            return;
        }
        for (int i = 0; i < 8; i++) { // 조합
            if (!isVisited[i]) {
                isVisited[i] = true;
                String name = names + friends[i];
                dfs(name, isVisited, datas);
                isVisited[i] = false;
            }
        }
    }

    // 조건대로 섰는지 체크
    private boolean check(String names, String[] datas) {
        for (String data : datas) {
            int position1 = names.indexOf(data.charAt(0)); // 프렌즈 포지션1
            int position2 = names.indexOf(data.charAt(2)); // 프렌즈 포지션2
            char op = data.charAt(3); // 수식
            int index = data.charAt(4) -'0'; // 간격
            if (op == '=') {
                if (!(Math.abs(position1 - position2) == index+1)) return false; //둘 포지션 차이를 구하기 위해선 index+1 을 해야함에 주의
            } else if (op == '>') {
                if (!(Math.abs(position1 - position2) > index+1)) return false;
            } else if (op == '<') {
                if (!(Math.abs(position1 - position2) < index+1)) return false;
            }
        }
        return true;
    }
}

 

내풀이(1)

문자열을 정리했지만 중복되는 결과가 들어가는 것이 문제가 됨.

ex)

BC와 CB가 같은 문자열로 취급되어 횟수가 2배가 됨.

BCFG의 결과와 BC와 CF, FG가 모두 계산되어버림.

 

앞으로는 예제 결과를 따라가보면서 예외처리를 잘 정리하고 시작해야겠다.

 

 

import java.io.*;
import java.util.*;

class Solution {
    ArrayList<Character> charList = new ArrayList<Character>();
    StringBuilder sb = new StringBuilder();
    Map<String, Integer> map = new HashMap<String, Integer>();
    boolean[] used = new boolean['Z'-'A'+1];
    
    public String[] solution(String[] orders, int[] course) {
        String[] answer = {};
        for(int i = 0; i < orders.length; i++){
            //for(int j = 0; j < course.length; j++){
                rec_func(1, orders[i], 2);
            //}
            
        }
        
        ArrayList<String> arr = new ArrayList<String>();
        for(String key : map.keySet()){
            if(map.get(key) > 1){
                arr.add(key);
            }else{
                continue;
            }
        }
        answer = new String[arr.size()];
        for(int i = 0 ; i < arr.size(); i++){
            answer[i] = arr.get(i);
        }
        return answer;
    }
    
    //K번째 음식 정하기
    public void rec_func(int k, String order,int range){
        int N = order.length();
       
        if(k == range + 1){//다 골랐다면 갱신
            // String result = sb.toString().StringArraySort();
            Collections.sort(charList);
            for(char ch : charList){
                sb.append(ch);
            }  
            if(map.containsKey(sb.toString())){
                int count = map.get(sb.toString());
                map.replace(sb.toString(),count + 1);
            }else{
                map.put(sb.toString(),1);
            }
            
             sb.setLength(0);
            
        }else{ 
            for(int temp = k-1; temp < N; temp++){
                if(used[order.charAt(temp)-'A'] == false){
                    used[order.charAt(temp)-'A'] = true;
                    //sb.append(order.charAt(temp));
                    charList.add(order.charAt(temp));
                    rec_func(k+1, order, range);
                }else{
                    continue;
                }
                used[order.charAt(temp)-'A'] = false;
                //sb.setLength(sb.length()-1);
                charList.remove(charList.size()-1);
            }
        }
    }
}

 

 

참고한풀이

 

 

아래와 같이 문자열 중괄호를 제거하려고 했지만 따로 할당하지 않으면 반영이 안 됨

 

Lv. 2 튜플 - 성공

내풀이

import java.io.*;
import java.util.*;
// split("},")
class Solution {
    String[] strArr = {};
    StringBuilder sb = new StringBuilder();
    Map<Integer,Integer> map = new HashMap<Integer,Integer>();
    
    public int[] solution(String s) {
        int[] answer = {};
        strArr = s.split("},");
        //중괄호 없애기 -> {{2 \ {2,1\ {2,1,3 \ {2,1,3,4}}
        for(int i = 0 ; i < strArr.length; i++){
            
            strArr[i] = strArr[i].replace("{","");
            strArr[i] = strArr[i].replace("}","");
            
            
        }
        
        ArrayList[] intArr = new ArrayList[strArr.length];
        // 문자열 배열 원소 개수 -> strArr.length;
        
        for(int i = 0 ; i < strArr.length; i++){
            intArr[i] = new ArrayList<Integer>();
        }
        
        for(int i = 0 ; i < strArr.length; i++){
            String[] tempArr = strArr[i].split(",");
            for(String sc : tempArr ){
                int sct = Integer.parseInt(sc);
                intArr[tempArr.length-1].add(sct);
            }
        }
        
      
        answer = new int[intArr.length];
        //순서대로 올라가면서 다음 원소 찾기
        for(int i = 0 ; i < intArr.length ; i++){
            for(int j = 0 ; j < intArr[i].size(); j++){
                int cand = (int)intArr[i].get(j);
                
                //처음 보는 숫자라면 추가.
                if(!map.containsKey(cand)){
                    sb.append(cand + ",");
                    //추가한 후 사용 여부 남기기
                    map.put(cand,cand);
                }else{
                    continue;
                }
                
            }
        }
        sb.setLength(sb.length()-1);
        System.out.println(sb.toString());
        String[] resultArr = sb.toString().split(",");
        for(int i = 0 ; i < resultArr.length; i++){
            answer[i] = Integer.parseInt(resultArr[i]);
        }
        return answer;
    }
}

 

 

 

에러)행렬의 M과 N을 거꾸로 할당해서 에러 발생. 행과 열 헷갈리지 않기.

에러)리턴 전에 정렬해보기

내풀이(1) : 정확도 90%

재귀함수를 사용하면 7번케이스를 통과하지 못한다고 함. -> 반복문으로 돌리는 게 낫다고 함.

class Solution {   
    //오른쪽, 아래, 왼쪽, 위쪽
    int[][] dir = {{0,1},{1,0},{0,-1},{-1,0}};
    boolean[][][] visited = {{{}}};
    ArrayList<Integer> result = new ArrayList<Integer>();
    
    int N = 0;
    int M = 0;
    public int[] solution(String[] grid) {
        int[] answer = {};
        visited = new boolean[grid.length][grid[0].length()][4];
        N = grid[0].length();
        M = grid.length;
        for(int i = 0 ; i < grid.length; i++){
            for(int j = 0; j < grid[0].length(); j++){
                dfs(i,j,0,grid, 1);
                dfs(i,j,1,grid, 1);
                dfs(i,j,2,grid, 1);
                dfs(i,j,3,grid, 1);
            }
        }
        answer = new int[result.size()];
        for(int i = 0; i < result.size(); i++){
            answer[i] = result.get(i);
        }
        Arrays.sort(answer);
        return answer;
    }
    public void dfs(int row, int col , int direct, String[] grid,int count){
        //지나간 적이 있다면
        if(visited[row][col][direct] == true){
            if(count == 1){
                return;
            }
            result.add(count-1);
            return;
        }else{
            visited[row][col][direct] = true;
            count++;
            int nr = 0;
            int nc = 0;
            int newdir = direct;
            //{0,1},{1,0},{0,-1},{-1,0} 
            if(grid[row].charAt(col) == 'S'){ //직진인 경우
                newdir = direct;
                nr = row + dir[direct][0];
                nc = col + dir[direct][1];
            }else if(grid[row].charAt(col) == 'L'){
                newdir = direct-1;
                if(newdir <= -1) newdir = 3;
                nr = row + dir[newdir][0];
                nc = col + dir[newdir][1];
            }else if(grid[row].charAt(col) == 'R'){
                newdir = direct+1;
                if(newdir >= 4) newdir = 0;
                nr = row + dir[newdir][0];
                nc = col + dir[newdir][1];
            }
            if(nr < 0){
                nr = M-1;
            } 
            if(nr >= M){
                nr = 0;  
            } 
            if(nc < 0) {
                nc = N-1;
            }
            if(nc >= N){
                 nc = 0;  
            }
            dfs(nr,nc,newdir, grid,count);
         }
    }

}

 

참고한 풀이

class Solution {
    // 상 우 하 좌 순서로 x, y좌표 더해줄 값 (방향 변수 d값이 아래 배열의 방향을 정함)
    int[] dx = {0, 1, 0, -1};
    int[] dy = {-1, 0, 1, 0};
    int w;  // 노드의 가로 크기
    int h;  // 노드의 세로 크기
    
    public int[] solution(String[] grid) {
        // 빛의 길이를 담을 배열
        ArrayList<Integer> arr = new ArrayList<>();
        w = grid[0].length();
        h = grid.length;
        // 가로세로 방문한 노드와 상 하 좌 우 방문 여부를 담은 배열
        boolean[][][] visit = new boolean[h][w][4];
        
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                for(int d = 0; d < 4; d++){
                    // 방문하지 않은 노드의 방향이 있을 경우
                    if(!visit[i][j][d]){
                        // 해당 노드부터 시작하는 빛의 길이를 계산후 반환
                        arr.add(getLightLen(grid, visit, i, j, d));
                    }
                }
            }
        }
        // 빛의 개수 만큼 배열 생성 후 빛의 길이 순서로 정렬
        int[] answer = new int[arr.size()];
        Collections.sort(arr);
        for(int i = 0; i < answer.length; i++) answer[i] = arr.get(i);
        
        return answer;
    }
    
    public int getLightLen(String[] grid, boolean[][][] visit, int y, int x, int d){
        int cnt = 0;    // 빛의 길이
        while(!visit[y][x][d]){
            cnt++;      // 빛의 길이 증가
            visit[y][x][d] = true;  // 현재 노드의 현재 방향 방문처리
            if(grid[y].charAt(x) == 'R') d = getDirection(d + 1);   // 방향 시계방향 회전
            else if(grid[y].charAt(x) == 'L') d = getDirection(d - 1);  // 방향 반시계방향 회전
            // 다음 방문할 위치계산 (중간에 배열의 크기를 더해서 음수가 되는것을 방지)
            x = (x + dx[d] + w) % w;    
            y = (y + dy[d] + h) % h; 
        }
        return cnt;
    }
    // 방향이 음수가 되거나 3을 넘어가면 보정해주는 기능
    public int getDirection(int direction){
        return direction < 0 ? 3 : direction % 4;
    }
}
출처: https://yline.tistory.com/121 [Y_LINE's_Repository:티스토리]

 

https://yline.tistory.com/121

[ 프로그래머스 - Java & Kotlin ] 빛의 경로 사이클 ( 자바 & 코틀린 )

 

Lv. 2 게임 맵 최단거리 - 성공

(N,M)이라는 표현을보고 N이 행인지 열인지 헷갈리는 상황이 생겨서 시간이 지체됨.

 

class Solution {
    int N = 0;
    int M = 0;
    int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};
    boolean[][] visited = {{}};
    int[][] howLong = {{}};
    
    public int solution(int[][] maps) {
        int answer = 0;
        
        N = maps.length;
        M = maps[0].length;
        visited = new boolean[N][M];
        
        howLong = new int[N][M];
        answer = bfs(0,0,maps);
        
        return answer;
    }
    
    public int bfs(int row, int col, int[][] maps){
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(row);
        queue.add(col);
        int count = 0;
        howLong[row][col] = count;
        while(!queue.isEmpty()){
            int r = queue.poll();
            int c = queue.poll();
            
            if(r == N-1 && c == M-1){
                return howLong[r][c] + 1;
            }
            if(visited[r][c] == true || maps[r][c] == 0){
                continue;
            }else{
                
                visited[r][c] = true;
                
                for(int i = 0; i < 4; i++){
                    
                    int nextR = r + dir[i][0];
                    int nextC = c + dir[i][1];
                    
                    if(nextR >= 0 && nextR < N && nextC >= 0 && nextC < M){
                        queue.add(nextR);
                        queue.add(nextC);
                        if(howLong[nextR][nextC] == 0){
                            howLong[nextR][nextC] = howLong[r][c] + 1;
                        }else{
                            howLong[nextR][nextC] = Math.min(howLong[nextR][nextC],howLong[r][c] + 1);

                        }
                        
                    }

                }
            }
        }
        return -1;
    }
    
    
}

 

참고한 풀이

import java.util.*;
 
class Solution {
    
    int[] dx = {0, 1, 0, -1};
    int[] dy = {-1, 0, 1, 0};
    boolean[][] visited;
    int n, m;
    
    public int solution(int[][] maps) {
        n = maps.length;
        m = maps[0].length;
        
        visited = new boolean[n][m];
        return bfs(0, 0, maps);
    }
    
    public int bfs(int x, int y, int[][] maps) {
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(x, y, 1));
        visited[x][y] = true;
        
        while(!q.isEmpty()) {
            Node node = q.poll();
            if(node.x == n - 1 && node.y == m - 1) return node.cost;
            
            for(int i = 0; i < 4; i++) {
                int nx = node.x + dx[i];
                int ny = node.y + dy[i];
                if(nx >= 0 && ny >= 0 && nx < n && ny < m) {
                    if(maps[nx][ny] == 1 && !visited[nx][ny]) {
                        visited[nx][ny] = true;
                        q.offer(new Node(nx, ny, node.cost + 1));
                    }
                }
            }
        }
        return -1;
    }
    
    public class Node {
        int x;
        int y;
        int cost;
        
        public Node(int x, int y, int cost) {
            this.x = x;
            this.y = y;
            this.cost = cost;
        }
    }
}

https://moonsbeen.tistory.com/100

[프로그래머스]게임 맵 최단거리 - JAVA