[프로그래머스] 자물쇠와 열쇠

참고: programmers.co.kr/learn/courses/30/lessons/60059

코딩테스트 연습 - 자물쇠와 열쇠

- key를 움직이는 부분이 잘 안 돼서 결국 풀이를 보고 풀었다.

- 도움받은 링크 : jellyinghead.tistory.com/28

 

- 구현 문제 

- key와 lock의 길이가 다른 점에 유의

- lock 과 key를 비교하기 위해서는 key.length * 2 + map.length 길이의 map을 생성 해줘서 

- key를 한칸씩 움직이며 ((0, 0)~ (key.length * 2 + map.length -1, key.length * 2 + map.length -1)) 해당 key가 lock에 맞는 key 위치 인 지 확인

- 맞지 않으면 rotate 4번 하면서 확인

key[y][row-x-1] = key[x][y] => ex. 길이 4인 n*n 행렬에서 회전할 경우 좌표(0,3) --> 좌표(3, 3) 이 됨.

- 4번 이후에도 맞지 않는다면 false 리턴

- N과 M 모두 크기가 20 이하이므로 worst case에도 4 * 58 * 58 * 20 * 20 정도의 실행 횟수를 가지므로 안전하다.

 

 

 

class Solution {
    
    private int[][] move(int[][] key, int dx, int dy) {
        int row = key.length;
        int col = key[0].length;
        int[][] nKey = new int[row][col];
        
        for(int i=0; i<row; i++) {
            for(int j=0; j<col; j++) {
                if(i+dx >= 0 && i+dx < row && j+dy >= 0 && j+dy < col) {
                    nKey[i][j] += key[i+dx][j+dy];   
                }
            }
        }
        return nKey;
    }
    
    private int[][] rotate(int[][] key) {
        int row = key.length;
        int col = key[0].length;
        int[][] nKey = new int[row][col];
        for(int i=0; i<row; i++) {
            for(int j=0; j<col; j++) {
                nKey[j][row-i-1] = key[i][j];
            }
        }
        
        return nKey;
    }
    
    private boolean isPassable(int[][] map, int[][] key) {
        int m = key.length;
        for(int i=m-1; i<map.length - (m -1); i++) {
            for(int j=m-1; j<map.length - (m-1); j++) {
                if(map[i][j] != 1) {
                    return false;
                }
            }
        }
        
        return true;
    }
    
    private int[][] getMap(int[][] key, int[][] lock) {
        int n = lock.length;
        int m = key.length;
        
        int map[][] = new int[n + 2*(m-1)][n + (2*m-1)];
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                map[m-1+i][m-1+j] = lock[i][j];
            }
        }
        
        return map;
    }
    
    
    public boolean solution(int[][] key, int[][] lock) {
        int n = lock.length;
        int m = key.length;
        
        int map[][] = getMap(key, lock);
        
        for(int i=0; i<4; i++) {
            key = rotate(key);
            for(int x=0; x<map.length - (m-1); x++) {
                for(int y=0; y<map.length - (m-1); y++) {
                    map = getMap(key, lock);
                    
                    for(int a=0; a<m; a++) {
                        for(int b=0; b<m; b++) {
                            map[x+a][y+b] += key[a][b];
                        }
                    }
                    
                    if(isPassable(map, key)) {
                        return true;
                    }
                    
                }
            }
        }
        
        return false;
    }
}