[프로그래머스] L3 자물쇠와 열쇠 / 2020 카카오 블라인드 채용 (Java)

카카오

[프로그래머스] L3 자물쇠와 열쇠 / 2020 카카오 블라인드 채용

[풀이]

이 문제를 풀기 위해 1) 배열의 회전과 2) 배열 이동 두 가지를 구현할 수 있어야 합니다.

 

1. 배열의 회전

배열의 회전

배열의 회전은 아래와 같은 반복문으로 가능합니다/

for(int i=0; i<M; i++){
 for(int j=0; j<M; j++){
  After[i][j] = Before[M-1-j][i];
 }
}

 

2. 배열 이동 컨셉

배열 이동

두 과정이 구현되었다면 key 배열을 한 칸씩 이동할 때마다 lock 배열과 겹치는 부분이 조건에 맞는지 확인합니다.

자세한 구현 과정을 아래 코드의 주석으로 달아두었습니다.

class Solution {
    static int N = 0, M = 0, NM = 0; // lock 배열 N, key 배열 M
    static int[][] cLock;
    public boolean solution(int[][] key, int[][] lock) {
        N = lock.length; // 초기 배열 사이즈 3
        M = key.length;  // 초기 배열 사이즈 3
        NM = N+(M-1)*2;  // 두 배열의 겹치는 부분을 확인하기 위한 하나의 배열
        
        // 확장된 맵의 중앙에 lock배열 복사
        cLock = new int[NM][NM];
        for(int i=M-1; i<M-1+N; i++){
            for(int j=M-1; j<M-1+N; j++){
                cLock[i][j] = lock[i-(M-1)][j-(M-1)];
            }
        }
 
        // 초기위치 + 90도씩 3번 회전
        for(int R=0; R<4; R++){
            if(R > 0) key = rotate(key);
            for(int i=0; i<=NM-M; i++){
                for(int j=0; j<=NM-M; j++){
                    int[][] cKey = new int[NM][NM];
                    // i,j에 key를 복사
                    for(int r = i; r<i+M; r++){
                        for(int c=j; c<j+M; c++){
                            cKey[r][c] = key[r-i][c-j];
                        }
                    }
                    // 복사된 key, lock으로 열 수 있는지 체크
                    if(check(cKey,cLock)) return true;
                }
            }
        }
        return false;
    }
    
    static boolean check(int[][] cKey, int[][] cLock){
        // 열쇠의 돌기:1 - 좌물쇠의 홈:0
        // NM배열에서 좌물쇠가 위치한 부분(M-1 ~ N+M-1)만 비교
        for(int i=M-1; i<N+M-1; i++){
            for(int j=M-1; j<N+M-1; j++){
                if(cLock[i][j] == 0 && cKey[i][j]==1) continue; // 홈&돌기
                else if(cLock[i][j]== cKey[i][j]) return false; // 홈&홈 or 돌기&돌기
            }
        }
        return true;
    }
    
    static int[][] rotate(int[][] key){
        // 배열을 90도 회전시키는 함수
        int[][] temp = new int[M][M];
        for(int i=0; i<M; i++){
            for(int j=0; j<M; j++){
                temp[i][j] = key[M-1-j][i];
            }
        }
        // 회전한 배열을 원배열에 복사 후 리턴
        for(int i=0; i<M; i++){
            for(int j=0; j<M; j++){
                key[i][j] = temp[i][j];
            }
        }
        return key;
    }
}