[프로그래머스] 자물쇠와 열쇠 / 2020 KAKAO BLIND RECRUITMENT - JAVA

🔗 문제 링크

[프로그래머스] 자물쇠와 열쇠 / 2020 KAKAO BLIND RECRUITMENT

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

 

📝 풀이 과정

열쇠를 자물쇠에 맞게 움직이며 비교하면서 답을 찾는 문제이다.

 

열쇠는 자물쇠를 벗어나게 대볼 수 있기 때문에 자물쇠를 기준으로 -M ~ +N까지의 범위로 비교해볼 수 있다.

만약 자물쇠가 모두 1(돌기)인경우까지 생각해 열쇠를 아예 벗어나게 대보는 경우도 고려했다.

 

함수에 y, x를 전달하고 해당 범위만큼 열쇠를 자물쇠에 대보는 연산을 수행한다.

예를 들어 (-2, -1)만큼 벗어나게 대본다고 가정했을 때, lock[0][0]과 key[1][2]를 비교해야 하기 때문에 - 연산을 통해 열쇠의 좌표값을 구해줄 수 있다. 만약 연산 결과가 key의 좌표를 벗어난다면 빈칸이 되므로 빈칸이라는 의미인 0을 대입해 주었다.

 

자물쇠의 좌표값과 비교했을 때 두개가 같다면 돌기+돌기, 빈칸+빈칸이기 때문에 모두 불가능한 경우로 false를 반환한다. 반복문이 중간에 종료되지 않고 정상적으로 종료되었다면 모든 홈을 매우는 경우로 true값을 리턴한다.

 

범위 안의 비교 연산을 모두 마쳤는데도 해결하지 못했다면 열쇠를 회전해서 다시 같은 연산을 수행해야 한다.

 

(0,0)(0,1)(0,2)(2,3)		(3,0)(2,0)(1,0)(0,0)
(1,0)(1,1)(1,2)(2,3)	=>	(3,1)(2,1)(1,1)(0,1)
(2,0)(2,1)(1,2)(2,3)		(3,2)(2,2)(1,2)(0,2)
(3,0)(3,1)(1,2)(2,3)		(3,3)(2,3)(1,3)(0,3)

열쇠를 시계방향으로 90도 회전하게 되면 기존 좌표가 오른쪽과 같이 이동하게 되는데 [i][j] -> [M - j - 1][i]의 규칙을 가지고 있다는 것을 알 수 있다. 이를 사용해 위의 연산이 실패하면 열쇠를 돌려가며 다시 수행하고 만약 4번째에도 실패한다면 열쇠가 360도 회전해 다시 원래의 상태로 돌아오기 때문에 열쇠로 자물쇠를 풀 수 없는 경우로 false를 반환한다.

 

💻 코드

class Solution {
    int N, M;
    public boolean solution(int[][] key, int[][] lock) {
        M = key.length;
        N = lock.length;
        for (int k = 0; k < 4; k++) {
            for (int y = -M; y < N; y++) {
                for (int j = -M; x < N; x++)
                    if (solve(key, lock, y, x)) return true;
            }
            
            int[][] rotate = new int[M][M];
            for (int i = 0; i < M; i++) 
                for (int j = 0; j < M; j++) 
                    rotate[i][j] = key[M - j - 1][i];
                    
            key = rotate;
        }
        
        return false;
    }
    
    boolean solve(int[][] key, int[][] lock, int y, int x) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int ky = i - y, kx = j - x, k; 
                
                if (ky < 0 || kx < 0 || ky >= M || kx >= M) k = 0;
                else k = key[ky][kx];
                if (lock[i][j] == k) return false;
            }
        }
        
        return true;
    }
}