(프로그래머스) 자물쇠와 열쇠

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

 

🐢 설명

자물쇠와 열쇠가 있고 열쇠를 좌우상하 움직여보고 90도씩 돌려보면서 겹치는 부분만 딱 들어 맞는다면 열린다고 판정하고 그외의 경우는 아니라고 해야하는 문제이다. 이때 자물쇠와 열쇠의 크기가 다를 수 있음에 유의하자.

 

다음과 같은 그림을 보면서 이해해보자.

Lock을 Key가 움직이면서 비교하기 위한 좌표 공간을 먼저 만들어준다. 이 공간은 원점을 기준으로 (key길이 - 1, key길이 - 1) 부터 (lock길이, lock길이)까지의 정사각형의 좌표평면을 갖게 된다.

이후 차례대로 모든 좌표에 대해서 확인을 해준다. 각 좌표에서 키를 둬보고 key 크기만큼 비교를 한다. 이때 좌표명면의 좌표값이 음수가 되거나 lock을 벗어난다면 이는 겹치지 않는 부분이므로 무시해줘야 한다.

따라서, 겹치는 부분에 대해서만 lock은 0이고, key가 1이라면  겹치는 부분에 해당하는 임시 배열을 만들어서 1을 체크해준다. 이때 lock과 key의 값이 같다면 매칭이 안되므로 false처리한다.

이후 겹치는 부분에 대해 모든 비교가 끝나면 해당 임시 배열과 , lock을 비교해서 둘다 0인 곳이 있다면 false를 처리한다. 이 경우는 겹치는 부분에 대해서는 들어 맞았지만 전체 lock이 들어 맞지는 않았다는 것이다. 이 외의 경우 매칭이 잘 된것이므로 true를 반환한다.

🐢코드

class Solution {
    static int[][] K;
    static int[][] L;
    static int klen;
    static int llen;
    static boolean ok;
    
    public boolean solution(int[][] key, int[][] lock) {
        
        K = key;
        L = lock;
        klen = K.length;
        llen = L.length;
        
        for (int d = 0; d < 4; d++) {
            if (match()) return true;
            else K = turn();
        }
        return false;
    }
    
    private static boolean match() {
        
        for (int y = 0 - klen + 1; y < llen; y++) {
            for (int x = 0 - klen + 1; x < llen; x++) {
                ok = true;
                
                // 겹치는 부분에 대한 임시 배열 공간
                int[][] tmp = new int[20][20];
                loop: for (int i = 0; i < klen; i++) {
                    for (int j = 0; j < klen; j++) {
                        int ny = y + i;
                        int nx = x + j;
                        
                        if (ny < 0 || ny >= llen || nx < 0 || nx >= llen) continue;
                        if (L[ny][nx] == K[i][j]) {
                            ok = false;
                            break loop;
                        }
                        // 겹치는 부분에 대해 맞물리는 곳을 체크함
                        if (L[ny][nx] == 0 && K[i][j] == 1) tmp[ny][nx] = 1;
                    }
                }
                
                // 겹치는 공간 배열과 자물쇠를 비교해서 다 들어맞는지 확인한다.
                // 아닌게 있다면 겹치는 부분에 자물쇠의 일부분만 맞물린 것이다.
                for (int i = 0; i < llen; i++) {
                    for (int j = 0; j < llen; j++) {
                        if (L[i][j] == 0 && tmp[i][j] == 0) {
                            ok = false;
                            break;
                        }
                    }
                }
                
                if (ok) return true;
            }
        }
        return false;
    }
    
    private static int[][] turn() {
        int[][] tmpK = new int[klen][klen];
        
        for (int i = 0; i < klen; i++) {
            for (int j = 0; j < klen; j++) {
                tmpK[j][klen - i - 1] = K[i][j];
            }
        }
        
        return tmpK;
    }
}

🐢 마무리