🤔 2020 카카오 블라인드 공채: 자물쇠와 열쇠 (Java)

📌 문제

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

잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다.

자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있습니다. 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다. 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않지만, 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다. 또한 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있습니다.

열쇠를 나타내는 2차원 배열 key와 자물쇠를 나타내는 2차원 배열 lock이 매개변수로 주어질 때, 열쇠로 자물쇠를 열수 있으면 true를, 열 수 없으면 false를 return 하도록 solution 함수를 완성해주세요.

📌 제한사항

• key는 M x M(3 ≤ M ≤ 20, M은 자연수)크기 2차원 배열입니다.
• lock은 N x N(3 ≤ N ≤ 20, N은 자연수)크기 2차원 배열입니다.
• M은 항상 N 이하입니다.
• key와 lock의 원소는 0 또는 1로 이루어져 있습니다.
  • 0은 홈 부분, 1은 돌기 부분을 나타냅니다.

📌 풀이

크게 3가지 기능을 만들면 되겠다고 생각했다.

1. lock을 3배로 늘리기
lock을 3배로 늘리면서, 실제 lock에 해당하지 않는 값은 3으로 설정해줬다. (나중에 계산할 때, 무시하기 위함)
홈을 발견하면 count++ (count는 lock의 홈의 개수를 의미)

2. 모든 홈이 채워졌는지 확인
- 실제 lock에 해당하지 않는 값(3)은 무시.
- lock과 key 모두 돌기라면 자물쇠를 풀 수 없다는 것.
- lock이 홈이고, key가 돌기면 홈이 채워졌다는 의미로 tempCount++
실제 lock의 홈의 개수(count)와 채워진 홈의 개수(tempCount)가 같으면, 해당 열쇠로 자물쇠를 풀 수 있다는 것.

3. key 배열 시계방향으로 90도 돌리기
총 4번 돌린다. (0도, 90도, 180도, 270도)
5번째는 360도로 0도와 같은 값이라서 돌리지 않는다.

📌 코드

public class 자물쇠와열쇠 {

    int count;
    
    public boolean solution(int[][] key, int[][] lock) {
        this.count = 0;
        lock = initLock(lock);
        for (int i = 0; i < 4; i++) {
            if (isMatch(key, lock)) return true;
            key = rotation(key);
        }
        return false;
    }

    private int[][] initLock(int[][] lock) {
        int n = lock.length;
        int[][] result = new int[n * 3][n * 3];
        for (int i = 0; i < result.length; i++) {
            for (int j = 0; j < result.length; j++) {
                if (i >= n && i < n * 2 && j >= n && j < n * 2) {
                    result[i][j] = lock[i - n][j - n];
                    if (result[i][j] == 0) this.count++;
                } else {
                    result[i][j] = 3;
                }
            }
        }
        return result;
    }

    private boolean isMatch(int[][] key, int[][] lock) {
        int keySize = key.length;
        int lockSize = lock.length;

        for (int i = 0; i <= lockSize - keySize; i++) {
            for (int j = 0; j <= lockSize - keySize; j++) {
                if (isMatch(key, lock, i, j)) return true;
            }
        }
        return false;
    }

    private boolean isMatch(int[][] key, int[][] lock, int x, int y) {
        int n = key.length;
        int tempCount = 0;
        for (int i = x; i < x + n; i++) {
            for (int j = y; j < y + n; j++) {
                if (lock[i][j] == 3) continue;
                if (lock[i][j] == 1 && key[i - x][j - y] == 1) return false;
                if (lock[i][j] == 0 && key[i - x][j - y] == 1) tempCount++;
            }
        }
        return count ==  tempCount;
    }

    private int[][] rotation(int[][] key) {
        int n = key.length;
        int[][] result = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                result[i][j] = key[n - 1 - j][i];
            }
        }
        return result;
    }
}

저작자표시

'Algorithm' 카테고리의 다른 글

🤔 BOJ16954 움직이는 미로 탈출 (Java)  (0)	2021.03.08
😄 2019 카카오 블라인드 공채: 후보키 (Java)  (0)	2020.05.03
🤔 2020 카카오 블라인드 공채: 자물쇠와 열쇠 (Java)  (0)	2020.04.28
😊 프로그래머스: Lv3. 입국 심사 (Java)  (0)	2020.04.25
😎 카카오 2019 겨울 인턴십: 불량 사용자(Lv3)  (0)	2020.04.05
🏗 카카오 2019 겨울 인턴십: 크레인 인형뽑기 게임(Lv2)  (0)	2020.04.01