[알고리즘 - 구현] 자물쇠와 열쇠

☀️ 시작

이번 문제는 2020 카카오 신입 개발자 블라인드 채용 1차 코딩 테스트의 3번 문항 '자물쇠와 열쇠' 문제이다. 카카오 해설을 보면 출제 의도는 2차원 배열을 다룰 수 있는가 이다.

📖 문제

문제 링크

이 문제는 MxM 크기의 key 배열과 NxN 크기의 lock 배열이 주어지는데 M <= N 이고, key 배열과 lock 배열을 일부 또는 전체 겹쳐서 lock 배열의 모든 좌표의 각각의 합이 1이 될 수 있는지를 구하는 문제이다. (기준은 lock이다) 이때 key 배열은 90도씩 4방향 모두 회전시킬 수 있다.

문제에서는 자물쇠의 모든 홈에 열쇠의 돌기를 맞출 수 있는지 물어보고 있고, 홈을 0, 돌기를 1로 표현한다.

즉, 아래와 같은 lock이 있다면

아래와 같이 key를 180도 돌리고 lock과 일부 겹치면 겹쳐진 key와 lock의 모든 좌표에서의 합이 각각 1이 되므로 자물쇠를 풀 수 있고, true를 반환하면 된다.

만약 어떤 방향으로 회전시키고 어떤 부분을 겹쳐도 모든 좌표의 합이 각각 정확히 1이 되지 못하면 자물쇠를 풀 수 없는 것으로, false를 반환하면 된다.

🧑🏻‍💻 풀이

이 문제를 풀기 위해서는 크게 두 가지의 로직을 구현해야 한다.

1. 배열을 90도씩 회전시키는 로직
2. key를 lock에 겹쳐지는 모든 경우의 수를 순회하고 좌표의 합이 정확히 1이 되는지 확인하는 로직

배열 회전

먼저 배열을 90도 회전시키는 로직의 경우 아래와 같이 직접 공식을 계산해서 로직으로 구현했다.

위와 같이 되므로 배열의 최대 좌표를 n이라 할 때 (위의 경우 n == 2) 새로운 x 좌표는 기존 y 좌표와 같고 새로운 y 좌표는 (n - 기존 x 좌표)와 같다. 이를 코드로 아래와 같이 구현했다. 주어진 배열 paddingKey를 90도 회전한 새로운 배열을 반환한다.

코드는 새로운 좌표의 x, y 좌표 자체를 구하는게 아니라 기존에 위치했을 (90도 회전 이전) 위치에 가서 값을 가져오도록 구현했기 때문에 현재의 x와 y좌표가 이전엔 어디에 있었을까? 를 계산해야 하고 따라서 현재 x는 이전의 (n - y)에서, 현재의 y는 이전의 x에서 값을 옮겨오면 된다.

public int[][] rotateKey(int M, int[][] paddingKey) {
    int[][] rotatedKey = new int[paddingKey.length][paddingKey.length];

    // M은 배열의 크기로, maxIndex는 좌표의 최대값
    int maxIndex = M - 1;
    for(int i = 0 ; i < M ; i++) {
        for(int j = 0 ; j < M ; j++) {
            // 90도 회전시키는 부분
            rotatedKey[i][j] = paddingKey[maxIndex - j][i];
        }
    }

    return rotatedKey;
}

key배열을 lock배열에 겹치기

이제 위에서 만든 배열 회전 메서드를 통해 key 배열을 4방향으로 회전시켜가며 lock에 겹쳐봐야한다. lock에 key가 겹치는 것은 아래와 같은 경우가 모두 포함되어야 한다.

따라서, lock과 key를 담을 수 있는 더 큰 배열이 필요하다. lock을 키워도 되고, key를 키워도 되고 다양한 방법이 있겠지만 key를 키우는 방법으로 문제를 풀었다.

key가 MxM일 때 위 그림처럼 좌상단, 우하단에 한 좌표씩 겹치는 경우까지 모두 포함하려면 패딩된 키 배열의 크기는 M x 2 + (N - 2) 여야 한다. (카카오 해설에선 그냥 M <= N 이므로 lock 배열 NxN을 3배 늘려서 풀었다)

그렇게 key를 늘려 아래와 같은 상태로 만든다. lock은 개념적으로 key의 한가운데 위치하는 상태이다.

그리고나서 이제 key를 좌측 상단에서 우측 하단까지 이동시키며 lock과 겹치는 부분의 좌표 합이 각각 1인지, 그리고 겹치지 않는 나머지 lock의 좌표 값이 1인지 확인한다. key 배열은 패딩된 key 배열에서 (0, 0)부터 (N + (M - 1), N + (M - 1)) 까지 이동할 수 있다. 편하게 shift하기 위해 메서드를 만들어 사용했다.

아래 메서드에서 M까지만 순회하는 이유는 어차피 현재 paddingKey의 좌측 상단 MxM에만 key가 위치해있기 때문이다.

public int[][] shiftKey(int M, int[][] paddingKey, int startX, int startY) {
    // 매번 새로운 배열을 만들어서 반환
    int[][] shiftedKey = new int[paddingKey.length][paddingKey.length];

    for (int i = 0 ; i < M ; i++) {
        for (int j = 0 ; j < M ; j++) {
            // 이동 작업
            shiftedKey[i + startX][j + startY] = paddingKey[i][j];
        }
    }

    return shiftedKey;
}

실제 코드에서는 아래와 같이 순회하면서 shiftKey()를 호출해 shift된 배열을 얻는다.

int shiftSize = lock.length + key.length - 1;
for (int startX = 0 ; startX < shiftSize ; startX++) {
    for (int startY = 0 ; startY < shiftSize ; startY++) {
        int[][] shiftedKey = shiftKey(key.length, rotatedKey, startX, startY);
        ...

그리고 위 for-loop 안에서 아래와 같이 lock과의 비교를 수행한다.

// 여기서 lock과의 비교 수행
boolean isOne = true;
for (int x = 0; x < lock.length ; x++) {
    for (int y = 0 ; y < lock.length ; y++) {
        // lock 기준 비교이므로 lock에서의 (x, y)를 shiftKey에서의 좌표로 바꿔주어야 한다.
        int keyX = key.length - 1 + x;
        int keyY = key.length - 1 + y;

        if (lock[x][y] + shiftedKey[keyX][keyY] != 1) {
            isOne = false;
        }
    }
    if (!isOne) {
        // 하나의 좌표라도 합이 1이 아니면 해당 shift는 실패
        break;
    }
}
if (isOne) {
    // 한번이라도 shiftedKey의 모든 좌표 합이 1이 된적이 있으면 자물쇠를 풀 수 있는 것, true 반환
    return true;
}
// 아니면 다음 shiftedKey와 비교 진행
// 모든 경우의 수에서 isOne이 false가 되면 최종 false 반환

위 과정은 하나의 방향에 대해 shift를 수행한 것이므로 위 과정은 각각 다른 방향으로 4번 수행되어야 한다.

전체 코드

github 링크

참고자료

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