Programmers - 자물쇠와 열쇠 with JAVA

 

 

 

문제

자물쇠와 열쇠가 주어지고 열쇠는 회전이 시계방향으로 90도 회전이 가능하다. 자물쇠와 열쇠의 상호간 돌기와 홈이 딱 맞으면 자물쇠를 풀 수 있다. 해당 열쇠로 자물쇠를 풀 수 있는지 판단하다.

 

 

 

로직

1. 맵 생성 - 자물쇠 크기의 3배로 설정

2. 맵에 자물쇠 설치

3. 키를 0도 - 90도 - 180도 - 270도 회전, 총 4회 반복

4. 키는 0,0으로 시작해 (0, 1), (0, 2) .... (1, 0), (1, 1) 과 같이 이동을 한다.

(+연산을 통해 키 움직임)

5. 이동시마다 자물쇠가 풀리는지 체크

6. 키 제거

(- 연산을 통해 키 제거)

 

추가적으로, 키와 자물쇠가 만나 2가되면 열리지 않는걸로 처리한다. 

 

 

 

추가적으로 회전 함수는 암기해두는 것이 좋다.

new_key[y][x의길이-x-1] = key[x][y];

 

 

 

 

 

코드

class Solution {
    public boolean solution(int[][] key, int[][] lock) {
        int n = lock.length;
        int m = key.length;
        int[][] map = new int[3*n][3*n];
        for(int x=0; x<n; x++){
            for(int y=0; y<n; y++){
                map[x+n][y+n] = lock[x][y];
            }
        }
        for(int k=0; k<4; k++){
            key = rotation(key);
            for(int x=0; x<2*n+1; x++){
                for(int y=0; y<2*n+1; y++){
                    for(int i=0; i<m; i++){
                        for(int j=0; j<m; j++){
                            map[i+x][j+y] += key[i][j];
                        }
                    }
                    int count = 0;
                    for(int i=0; i<n; i++){
                        for(int j=0; j<n; j++){
                            if(map[i+n][j+n] == 1){
                                count += 1;
                            }
                        }
                    }
                    if(count == n*n){
                        return true;
                    }
                    for(int i=0; i<m; i++){
                        for(int j=0; j<m; j++){
                            map[i+x][j+y] -= key[i][j];
                        }
                    }
                }
            }
        }
        return false;
    }
    public static int[][] rotation(int[][] key){
        int m = key.length;
        int[][] result = new int[m][m];
        for(int x=0; x<m; x++){
            for(int y=0; y<m; y++){
                result[y][m-x-1] = key[x][y];
            }
        }
        return result;
    }
}