프로그래머스 Lv3 자물쇠와 열쇠

2020 카카오 코딩 테스트 1차 문제

문제풀이

https://tech.kakao.com/2019/10/02/kakao-blind-recruitment-2020-round1/

2020 신입 개발자 블라인드 채용 1차 코딩 테스트 문제 해설

여기에 써있는 풀이를 그대로 구현했다.

1. 자물쇠가 N*N 행렬이라면, 3N*3N 매트릭스를 만든 후, 가운데 자물쇠를 배치한다.

2. 열쇠를 매트릭스에 올려놓고 한 칸씩 움직이며 3N*3N 행렬의 가운데가 모두 1이 되는지 확인한다.

3. 2에서 찾지 못한다면 열쇠를 90도 돌려서 다시 2 과정을 수행한다.

4. 4번 돌렸는데도(360도) 찾지 못한다면 불가능한 경우이다.

Python Code

class Solution {
    public boolean solution(int[][] key, int[][] lock) {
        int lockLen = lock.length;
        int[][] l = new int[lockLen*3][lockLen*3];
        for(int i=0;i<lockLen;i++) {
            for(int j=0;j<lockLen;j++) {
                l[i+lockLen][j+lockLen] = lock[i][j];
            }
        }
        for(int r=0; r<4;r++) {
            key=rotate(key);
            boolean check = compare(key,l);
            if(check)return true;
        }
        return false;
    }
    public int[][] rotate(int[][] key){
        int len = key.length;
        int[][] ans = new int[len][len];
        for(int i=0;i<len;i++) {
            for(int j=0;j<len;j++) {
                ans[j][len-1-i] = key[i][j];
            }
        }
        return ans;
    }
    public boolean compare(int[][] key, int[][] lock) {
        int keyLen = key.length;
        int lockLen = lock.length;
        int diff = lockLen-keyLen;
        for(int iMove=0; iMove<=diff;iMove++) {
            for(int jMove=0; jMove<=diff;jMove++) {
                int[][] tempKey = new int[lockLen][lockLen];
                for(int i=0;i<keyLen;i++) {
                    for(int j=0;j<keyLen;j++) {
                        tempKey[i+iMove][j+jMove] = key[i][j];
                    }
                }
                boolean check = check(tempKey,lock);
                if(check)return true;
            }
        }
        return false;
    }
    public boolean check(int[][] key, int[][] lock) {
        int len = lock.length/3;
        for(int i=len;i<len*2;i++) {
            for(int j=len;j<len*2;j++) {
                if(key[i][j]+lock[i][j]!=1) {
                    return false;
                }
            }
        }
        return true;
    }
}

Line 17 : 열쇠를 90도 회전시키는 함수이다.

Line 27 : 열쇠를 3N*3N 행렬에 올려놓고 한칸씩 움직이는 과정이다.

Line 45 : 열쇠와 자물쇠가 맞는지 확인하는 함수이다.

문제 링크

프로그래머스