2020 - 자물쇠와 열쇠

https://programmers.co.kr/learn/courses/30/lessons/60059

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

[ 문제풀이 ]

4방향 회전한 Key로 자물쇠 Lock을 채울 수 있는지를 확인하는 전형적인 완전 탐색 문제이다. key를 회전하는 것은 쉬운데 회전한 후 lock과 어떻게 비교할 것인지가 조금 난해한 문제이다.

​모든 key를 주어진 lock으로 비교하기에는 인덱스 관리하기가 상당히 까다롭다.

이를 쉽게 해결하기 위해 기존의 lock을 확장시켜 인덱스를 넓혀주도록 하자. Key의 크기 M은 항상 lock의 크기 N 이하이기 때문에 모든 경우의 수를 확인하기 위해서 N을 3배 정도로 확장시켜 주면 된다.

필요한 4방향의 Key와 확장된 Lock을 준비하였다면 하나씩 비교해가며 가능한지 판단해주면 된다.

class Solution {
    int N, M;
    int[][] Lock;
    int[][][] Key;
    
    public boolean solution(int[][] key, int[][] lock) {
        int emptyCount = 0; //lock의 빈 공간 개수
        M = key.length;
        N = lock.length;
        
        Lock = new int[N * 3][N * 3];
        //lock 확장
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                Lock[i + N][j + N] = lock[i][j];
                if (lock[i][j] == 0) emptyCount++;
            }
        }
        
        Key = new int[4][M][M];
        //key 4방향 회전
        rotateKey(key);
        
        //가능한 Key를 Lock과 비교
        for (int t = 0; t < 4; ++t) {
            for (int i = 0; i <= N * 3 - M; ++i) {
                for (int j = 0; j <= N * 3 - M; ++j) {
                    boolean flag = true;
                    int cnt = 0; //빈 공간을 채운 개수
                    
                    for (int y = 0; y < M; ++y) {
                        if (!flag) break;
                        for (int x = 0; x < M; ++x) {
                            if (!flag) break;
                            
                            int yy = i + y; int xx = j + x;
                            
                            //(yy, xx)가 Lock의 범위라면
                            if (yy >= N && yy < N * 2 && xx >= N && xx < N * 2) { 
                                //Lock : Key가 0 : 0이거나 1 : 1인 경우는 성립 x
                                if ((Key[t][y][x] + Lock[yy][xx]) % 2 == 0) {
                                    flag = false;
                                    break;
                                }
                                
                                //Lock : Key가 0 : 1인 경우는 가능하지만 빈 공간을 채우는 것이 아님
                                if (Key[t][y][x] == 0 && Lock[yy][xx] == 1) continue;
                                
                                //빈 공간을 채웠기 때문에 cnt 1증가
                                cnt++;
                            }
                        }
                    }
                    
                    //빈 공간을 모두 채웠다면
                    if (cnt == emptyCount) return true;
                }
            }
        }
        
        return false;
    }
    
    public void rotateKey(int[][] key) {
        for (int t = 0; t < 4; ++t) {
            for (int i = 0 ; i < M; ++i) {
                for (int j = 0; j < M; ++j) {
                    Key[t][i][j] = key[i][j];
                }
            }
            
            //시계방향 90도 회전
            for (int i = 0 ; i < M; ++i) {
                for (int j = 0; j < M; ++j) {
                    key[j][M - i - 1] = Key[t][i][j];
                }
            }
        }
    }
}