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

🖇️ 문제 링크

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

고고학자인 "튜브"는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠 와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다. 잠겨있는 자물쇠는 격자 한 칸의 크기가 인 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 크기인 정사각 격자 형태로 되어 있습니다.

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

 

---

📝 문제 분석

Key는 회전 횟수에 따라 4가지 종류가 있을 수 있습니다.

Lock의 (0, 0)부터 (N - 1, N - 1)까지 4가지 종류의 키를 차례대로 맞춰봅니다.

Lock의 홈이 모두 맞춰진다면 true 리턴

 

 

---

⌨️ 코드

class Solution {
    public boolean solution(int[][] key, int[][] lock) {
        int M = key.length, N = lock.length;
        int size = 2 * M + N - 2;
        int[][] map = new int[size][size];
       	boolean flag = false; 
        
        for(int[] ints : lock)
            for(int n : ints)
                if(n == 0)
                    flag = true;
        if(!flag)
            return true;
                
        
        // 키를 어디서든 대볼 수 있게 자물쇠 배열 확장, 중간에 자물쇠 값 저장
        for(int i = M - 1; i < M + N - 1; i++)
            for(int j = M - 1; j < M + N - 1; j++)
                map[i][j] = lock[i - (M - 1)][j - (M - 1)];
        
        for(int d = 0; d < 4; d++) {
            for(int i = 0; i < M + N - 1; i++) {
                for(int j = 0; j < M + N - 1; j++) {
                    // 딱 맞는지 확인
                    if(chk(map, key, i, j, M, N))
                        return true;
                }
            }
            // 회전
            key = rotate(key);
        }
        
        return false;
    }

    static boolean chk(int[][] map, int[][] key, int y, int x, int m, int n) {
        boolean check = true;
        // key 다 더해봄
        for(int i = y; i < y + m; i++)
            for(int j = x; j < x + m; j++)
                map[i][j] += key[i - y][j - x];
        
        // 자물쇠 영역에 딱 맞는지 확인
        for(int i = m - 1; i < m + n - 1; i++)
            for(int j = m - 1; j < m + n - 1; j++)
                if(map[i][j] != 1) check = false;
        
        // 원상복구
        for(int i = y; i < y + m; i++)
            for(int j = x; j < x + m; j++)
                map[i][j] -= key[i - y][j - x];
        
        return check;
    }

    static int[][] rotate(int[][] key) {
        int n = key.length;
        int[][] tmp = new int[n][n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                tmp[i][j] = key[j][n - i - 1];
        return tmp;
    }
}

 

 

 

 

Uploaded by Notion2Tistory v1.1.0