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

코딩테스트 연습 - 자물쇠와 열쇠 | 프로그래머스 (programmers.co.kr)

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

어떻게 생각하고 문제를 풀었는가?

MxM 배열의 키는 회전이 가능하고 이동할 수 있습니다.

주어진 예시에서 알 수 있듯, 이동한 키의 원소 중 하나라도 자물쇠의 원소와 비교할 수 있다면 키의 역할을 수행할 수 있습니다.

키 배열의 원소들이 모두 자물쇠 배열의 원소들과 대응하지 않아도 된다.

주어진 조건에서 키 배열의 크기 M은 항상 자물쇠 배열의 크기 N 이하입니다. 따라서 키 배열의 마지막 열/행이 자물쇠 배열의 첫번째 열/행과 비교되는 케이스부터 키 배열의 첫번째 열/행이 배열의 마지막 열/행과 비교되는 케이스까지 가능하도록 -(N-1) ~ (N-1)의 이동에 대해 테스트가 이루어져야 합니다.

 

키 배열의 회전은 자물쇠와 대응하기 위해 90도의 회전씩만 수행할 수 있습니다.(자물쇠 홈이 사각형이기 때문.) 90도의 회전은 다음 그림과 같이 계산할 수 있습니다.

시계방향으로 90도 회전은 A[i][j]를 A[N-1-j][i]의 위치로 이동시킨다.

모든 회전, 이동에 대해 테스트를 수행하여 참이 되는 케이스를 찾으면 true를 반환함으로서 문제를 해결할 수 있습니다.

코드

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

테스트를 통과하는 코드를 작성하였습니다.

0도, 90도, 180도, 270도 회전을 수행한 후, 키 배열을 이동하여 자물쇠를 열 수 있다면 true를 리턴, 아니라면 다른 케이스를 확인합니다.

자물쇠의 0값을 키의 1값으로 채울 수 없거나, 자물쇠의 1값과 키의 1값이 같은 위치에서 발생한다면 false를 반환해야 합니다. 자물쇠 배열의 원소와 키 배열의 원소가 대응되지 않더라도 자물쇠 배열 원소의 값이 0이 되는지 확인하여야 옳은 결과를 반환할 수 있습니다.