2020 KAKAO BLIND RECRUITENT : 자물쇠와 열쇠

*** 본 풀이는 java언어를 사용하였습니다. ***

문제 보러가기

 

핵심 요약

Key가 Lock의 구멍에 정확히 일치하는가 (key가 회전 가능)

2차원 배열에 대한 이해 / 깉은 , 얕은 복사에 대한 이해 필요

 

여러가지 풀이법이 있겠지만 기존 Lock의 크기로 Key를 비교하기엔 여간 까다로운게 아니다.

그럼 어떻게 해야할까?

Lock의 크기를 확장하면 된다.

Lock의 배열의 크기를 Key가 바로 검증할 수 있는 크기로 확장하고, Lock을 중앙에 배치하면

다음과 같이 Key를 통해 바로 탐색이 가능해 진다.

 

확장 크기는 lock.length + (key.length - 1) * 2를 통해 확장할 수 있다.

 

그 후 Key가 확장 배열에 값을 더하면서 Lock의 배열 값들이 모두 1이 들어있는지를 판단하면 된다.

(Lock의 값들이 모두 1이라면 Lock의 모든 홈을 채운 것이기 때문이다)

 

한 사이클이 돌아가면 초기화 과정을 통해 key를 더하기 전의 상태로 바꿔놓는다.

 

key가 Lock의 오른쪽 하단까지 순회해도 Lock의 원소값들이 1 이 나오지 않는다면 회전을 시킨다.

(필자의 경우 시계방향 회전으로 구현했다)

 

그 후 위의 사이클 반복..

 

한 바퀴를 다 돌아도 Lock의 원소값들이 1 이 나오지 않는다면 Key가 Lock에 맞지 않는 것으로 false를 리턴

 

위의 과정을 잘 생각해보고 구현하면 비교적 쉽게 구현이 가능 할 것이다.

 

제출 코드

public class Solution {
    private int[][] key;
    private int[][] lock;
    private int centerStartIndex;
    private int centerEndIndex;

    public boolean solution(int[][] key, int[][] lock) {
        final int rotateCount = 4;
        this.key = key;
        this.lock = lock;
        centerStartIndex = key.length - 1;
        centerEndIndex = centerStartIndex + lock.length;

        int[][] copyLock = createExpandedLock(); // 확장 Lock 생성

        for (int r = 0; r < rotateCount; r++) {

            // 왼쪽 끝 부터 오른쪽 아래까지 비교
            int to = copyLock.length - key.length;
            for (int i = 0; i <= to; i++) {
                for (int j = 0; j <= to; j++) {
                    // key 삽입
                    int x = 0;
                    int y;
                    for (int k = i; k < key.length + i; k++) {
                        y = 0;
                        for (int l = j; l < key.length + j; l++) {
                            copyLock[k][l] += key[x][y++];
                        }
                        x++;
                    }

                    if (isFitKeyToLock(copyLock)) {
                        return true;
                    }
                    copyLock = createExpandedLock();
                }
            }

            // 회전
            this.key = rotateKey(key);
        }
        return false;
    }

    private int[][] createExpandedLock() {
        int expandedSize = lock.length + (key.length - 1) * 2;
        return insertLockToCenter(new int[expandedSize][expandedSize]);
    }

    private int[][] insertLockToCenter(int[][] copyLock) {
        int x = 0;
        int y;
        for (int i = centerStartIndex; i < centerEndIndex; i++) {
            y = 0;
            for (int j = centerStartIndex; j < centerEndIndex; j++) {
                copyLock[i][j] = lock[x][y++];
            }
            x++;
        }
        return copyLock;
    }

    private boolean isFitKeyToLock(int[][] copyLock) {
        for (int i = centerStartIndex; i < centerEndIndex; i++) {
            for (int j = centerStartIndex; j < centerEndIndex; j++) {
                if (copyLock[i][j] != 1) return false;
            }
        }
        return true;
    }

    public int[][] rotateKey(int[][] key) {
        int keySize = key.length;
        int[][] copyKey = new int[keySize][keySize];

        for (int i = 0; i < keySize; i++) {
            for (int j = 0; j < keySize; j++) {
                copyKey[i][j] = key[keySize - 1 - j][i];
            }
        }

        for (int i = 0; i < copyKey.length; i++) {
            key[i] = copyKey[i].clone();
        }
        return key;
    }
}

 

테스트 코드

public class SolutionTest {
    private Solution solution;

    @Before
    public void setUp() throws Exception {
        solution = new Solution();
    }

    @Test
    public void testCase_1() {
        int[][] key = new int[][]{{0, 0, 0}, {1, 0, 0}, {0, 1, 1}};
        int[][] lock = new int[][]{{1, 1, 1}, {1, 1, 0}, {1, 0, 1}};

        assertThat(solution.solution(key, lock)).isEqualTo(true);
    }

    @Test
    public void testCase_2() {
        int[][] key = new int[][]{{0, 0}, {1, 0}};
        int[][] lock = new int[][]{{1, 1, 1}, {1, 1, 0}, {1, 0, 1}};

        assertThat(solution.solution(key, lock)).isEqualTo(false);
    }

    @Test
    public void testCase_3() {
        int[][] key = new int[][]{{0, 0}, {1, 0}};
        int[][] lock = new int[][]{{1, 1, 1}, {1, 1, 0}, {1, 1, 1}};

        assertThat(solution.solution(key, lock)).isEqualTo(true);
    }

    @Test
    public void testCase_4() {
        int[][] key = new int[][]{{1, 0}, {1, 0}};
        int[][] lock = new int[][]{{1, 1, 1}, {1, 1, 1}, {0, 0, 1}};

        assertThat(solution.solution(key, lock)).isEqualTo(true);
    }

    @Test
    public void 회전이_잘_되는가() {
        int[][] key = new int[][]{{1, 1}, {0, 0}};

        // 90도 회전
        key = solution.rotateKey(key);
        assertThat(key).isEqualTo(new int[][]{{0, 1}, {0, 1}});

        // 180도 회전
        key = solution.rotateKey(key);
        assertThat(key).isEqualTo(new int[][]{{0, 0}, {1, 1}});

        // 270도 회전
        key = solution.rotateKey(key);
        assertThat(key).isEqualTo(new int[][]{{1, 0}, {1, 0}});

        // 360도 회전
        key = solution.rotateKey(key);
        assertThat(key).isEqualTo(new int[][]{{1, 1}, {0, 0}});
    }
}

 

회고

이번 문제는 2차원 배열에 대한 이해가 있어야 풀 수 있는 문제 인 것 같다.

더불어 얕은 복사와 깊은 복사에 대한 이해도 필요하다.

 

필자도 다음과 같은 실수로 시간을 많이 잡아 먹었다.

Key를 회전시키는 과정에서 복사된 copyKey를 참조시키게 했더니 예상한 값이 나오지 않는 현상이 발생했다.

key = copyKey;

이유는 얕은 복사이였기 때문..

 

따라서 다음과 같이 깊은 복사로 바꿔줘야 정상적으로 값이 들어간다.

key = copykey.clone();

 

꽤나 시간을 잡아먹었던 문제.. 2차원 배열에 대해 제대로 이해하지 못했다고 생각하고 반성해야겠다..