[programmers] KAKAO 2020 BLIND RECRUITMENT - 자물쇠와 열쇠

곽형조 (KCena)·2020년 9월 1일
0

자물쇠와 열쇠

이 문제는 다차원 배열을 이용해 전체 경우를 탐색하여 해당 자물쇠를 열쇠로 열 수 있는지 검사하는 문제이다. 문제에서 주어지는 N과 M의 제한이 크지 않아 모든 경우를 탐색해도 시간 초과가 발생하지 않을 것이라 생각했다.

어떻게 풀었는가?

내가 푼 방식은 아래와 같다.

  1. N * N 형태의 자물쇠를 상,하,좌,우로 M - 1 만큼 확장한다.
  2. 확장한 자물쇠 배열의 (0,0) 부터 key의 원소들을 key의 크기만큼 lock의 원소에 하나씩 더해준다.
    2-1. key를 대입했을 때 자물쇠가 모두 1로 채워져 있다면 True를 반환한다.
    2-2. 만약 0(자물쇠의 모든 홈이 채워지지 않음)이나 2(자물쇠와 열쇠의 돌기가 만남)라면 이는 열리지 않는 것이므로 False를 반환한다.
  3. key를 90도 시계방향(또는 반시계)으로 회전하여 1~2 단계를 반복한다.

코드

각각의 단계는 pytest를 적용하여 테스트를 진행하였다.

자물쇠 배열 확장하기

def lock_expansion(lock, lock_len, key_len):
    expanded_len = 2 * key_len + lock_len - 2
    expanded = [[0] * expanded_len for _ in range(expanded_len)]
    for i in range(lock_len):
        for j in range(lock_len):
            expanded[i + key_len - 1][j + key_len - 1] = lock[i][j]
    return expanded
    
def test_lock_expansion():
    assert lock_expansion([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 3, 3) == [
        [0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
        [0, 0, 1, 1, 1, 0, 0],
        [0, 0, 1, 1, 0, 0, 0],
        [0, 0, 1, 0, 1, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
    ]
    assert lock_expansion(
        [[1, 1, 1, 1], [1, 1, 0, 1], [1, 0, 1, 1], [1, 0, 1, 0]], 4, 3) == [
               [0, 0, 0, 0, 0, 0, 0, 0],
               [0, 0, 0, 0, 0, 0, 0, 0],
               [0, 0, 1, 1, 1, 1, 0, 0],
               [0, 0, 1, 1, 0, 1, 0, 0],
               [0, 0, 1, 0, 1, 1, 0, 0],
               [0, 0, 1, 0, 1, 0, 0, 0],
               [0, 0, 0, 0, 0, 0, 0, 0],
               [0, 0, 0, 0, 0, 0, 0, 0],
           ]
    assert lock_expansion(
        [[1, 0, 1, 1, 1], [0, 0, 1, 1, 1], [0, 1, 0, 1, 1], [1, 1, 1, 1, 1],
         [1, 1, 1, 1, 1]], 5, 3) == [
               [0, 0, 0, 0, 0, 0, 0, 0, 0],
               [0, 0, 0, 0, 0, 0, 0, 0, 0],
               [0, 0, 1, 0, 1, 1, 1, 0, 0],
               [0, 0, 0, 0, 1, 1, 1, 0, 0],
               [0, 0, 0, 1, 0, 1, 1, 0, 0],
               [0, 0, 1, 1, 1, 1, 1, 0, 0],
               [0, 0, 1, 1, 1, 1, 1, 0, 0],
               [0, 0, 0, 0, 0, 0, 0, 0, 0],
               [0, 0, 0, 0, 0, 0, 0, 0, 0],
           ]
  • 자물쇠의 배열을 확장하는 함수 이름은 lock_expansion 으로 하였다. 인자는 key, lock의 길이, key의 길이 를 받는다. lock과 key는 모두 정사각형 이므로 가로든 세로든 상관없다.
  • expanded_len은 확장된 자물쇠 배열의 길이이다. 이 길이는 (key length - 1) + lock length + (key length - 1) 로 구할 수 있다.
  • list comprehension을 이용하여 미리 0으로 채워진 확장 배열을 만들어 놓고, 가운데에 lock 배열의 데이터를 넣어 반환한다.

자물쇠에 키를 넣어보기

def unlock(key, sy, sx, lock):
    for i in range(sy, sy + len(key)):
        for j in range(sx, sx + len(key)):
            lock[i][j] += key[i - sy][j - sx]
    return lock
    
    
def test_unlock():
    assert unlock([[0, 0, 0], [1, 0, 0], [0, 1, 1]], 0, 0, [
        [0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
        [0, 0, 1, 1, 1, 0, 0],
        [0, 0, 1, 1, 0, 0, 0],
        [0, 0, 1, 0, 1, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
    ]) == [
               [0, 0, 0, 0, 0, 0, 0],
               [1, 0, 0, 0, 0, 0, 0],
               [0, 1, 2, 1, 1, 0, 0],
               [0, 0, 1, 1, 0, 0, 0],
               [0, 0, 1, 0, 1, 0, 0],
               [0, 0, 0, 0, 0, 0, 0],
               [0, 0, 0, 0, 0, 0, 0],
           ]
    assert unlock([[0, 0, 0], [1, 0, 0], [0, 1, 1]], 0, 1, [
        [0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
        [0, 0, 1, 1, 1, 0, 0],
        [0, 0, 1, 1, 0, 0, 0],
        [0, 0, 1, 0, 1, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
    ]) == [
               [0, 0, 0, 0, 0, 0, 0],
               [0, 1, 0, 0, 0, 0, 0],
               [0, 0, 2, 2, 1, 0, 0],
               [0, 0, 1, 1, 0, 0, 0],
               [0, 0, 1, 0, 1, 0, 0],
               [0, 0, 0, 0, 0, 0, 0],
               [0, 0, 0, 0, 0, 0, 0],
           ]
    assert unlock([[0, 0, 0], [1, 0, 0], [0, 1, 1]], 1, 1, [
        [0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
        [0, 0, 1, 1, 1, 0, 0],
        [0, 0, 1, 1, 0, 0, 0],
        [0, 0, 1, 0, 1, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
    ]) == [
               [0, 0, 0, 0, 0, 0, 0],
               [0, 0, 0, 0, 0, 0, 0],
               [0, 1, 1, 1, 1, 0, 0],
               [0, 0, 2, 2, 0, 0, 0],
               [0, 0, 1, 0, 1, 0, 0],
               [0, 0, 0, 0, 0, 0, 0],
               [0, 0, 0, 0, 0, 0, 0],
           ]
    assert unlock([[0, 0, 0], [1, 0, 0], [0, 1, 1]], 4, 4, [
        [0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
        [0, 0, 1, 1, 1, 0, 0],
        [0, 0, 1, 1, 0, 0, 0],
        [0, 0, 1, 0, 1, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
    ]) == [
               [0, 0, 0, 0, 0, 0, 0],
               [0, 0, 0, 0, 0, 0, 0],
               [0, 0, 1, 1, 1, 0, 0],
               [0, 0, 1, 1, 0, 0, 0],
               [0, 0, 1, 0, 1, 0, 0],
               [0, 0, 0, 0, 1, 0, 0],
               [0, 0, 0, 0, 0, 1, 1],
           ]
    assert unlock([[0, 1, 0], [1, 1, 0], [1, 0, 1]], 2, 2, [
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 1, 0, 1, 1, 1, 0, 0],
        [0, 0, 0, 0, 1, 1, 1, 0, 0],
        [0, 0, 0, 1, 0, 1, 1, 0, 0],
        [0, 0, 1, 1, 1, 1, 1, 0, 0],
        [0, 0, 1, 1, 1, 1, 1, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
    ]) == [
               [0, 0, 0, 0, 0, 0, 0, 0, 0],
               [0, 0, 0, 0, 0, 0, 0, 0, 0],
               [0, 0, 1, 1, 1, 1, 1, 0, 0],
               [0, 0, 1, 1, 1, 1, 1, 0, 0],
               [0, 0, 1, 1, 1, 1, 1, 0, 0],
               [0, 0, 1, 1, 1, 1, 1, 0, 0],
               [0, 0, 1, 1, 1, 1, 1, 0, 0],
               [0, 0, 0, 0, 0, 0, 0, 0, 0],
               [0, 0, 0, 0, 0, 0, 0, 0, 0],
           ]
    assert unlock([[0, 1, 0], [1, 1, 0], [1, 0, 1]], 1, 0, [
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 1, 0, 1, 1, 1, 0, 0],
        [0, 0, 0, 0, 1, 1, 1, 0, 0],
        [0, 0, 0, 1, 0, 1, 1, 0, 0],
        [0, 0, 1, 1, 1, 1, 1, 0, 0],
        [0, 0, 1, 1, 1, 1, 1, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
    ]) == [
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 1, 0, 0, 0, 0, 0, 0, 0],
        [1, 1, 1, 0, 1, 1, 1, 0, 0],
        [1, 0, 1, 0, 1, 1, 1, 0, 0],
        [0, 0, 0, 1, 0, 1, 1, 0, 0],
        [0, 0, 1, 1, 1, 1, 1, 0, 0],
        [0, 0, 1, 1, 1, 1, 1, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
    ]
  • unlock은 인자로 key, 시작 행, 시작 열, 확장된 자물쇠 를 받는다.
  • 시작 좌표부터 자물쇠에 키를 대입하는 것은 각각의 (행, 열) index에 원소를 더한다. 테스트를 보면 더해진 결과가 어떻게 나오는지 알 수 있다.
  • key의 index는 무조건 (0, 0) 부터 시작해야 하므로 시작 행과 시작 열을 빼 주어야 한다.

자물쇠가 열리는지 확인하기

def is_open(lock, sy, sx, length):
    for i in range(sy, sy + length):
        for j in range(sx, sx + length):
            if lock[i][j] != 1:
                return False
    return True

def test_is_open():
    assert is_open([
        [0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
        [0, 1, 1, 1, 1, 0, 0],
        [0, 0, 2, 2, 0, 0, 0],
        [0, 0, 1, 0, 1, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
    ], 2, 2, 3) is False
    assert is_open([
        [0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
        [0, 1, 1, 1, 1, 0, 0],
        [0, 0, 1, 1, 1, 0, 0],
        [0, 0, 1, 1, 1, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
    ], 2, 2, 3) is True
    assert is_open([
        [0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
        [0, 1, 1, 1, 1, 0, 0],
        [0, 0, 1, 1, 1, 0, 0],
        [0, 0, 1, 2, 1, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
    ], 2, 2, 3) is False
    assert is_open([
        [0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
        [0, 1, 1, 1, 1, 0, 0],
        [0, 0, 1, 1, 1, 0, 0],
        [0, 0, 1, 0, 1, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
    ], 2, 2, 3) is False
    assert is_open([
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 1, 1, 1, 1, 0, 0],
        [0, 0, 1, 1, 0, 1, 0, 0],
        [0, 0, 1, 0, 1, 1, 0, 0],
        [0, 0, 1, 0, 1, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
    ], 2, 2, 3) is False
    assert is_open([
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 1, 1, 1, 1, 1, 0, 0],
        [0, 0, 1, 1, 1, 1, 1, 0, 0],
        [0, 0, 1, 1, 1, 1, 1, 0, 0],
        [0, 0, 1, 1, 1, 1, 1, 0, 0],
        [0, 0, 1, 1, 1, 1, 1, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
    ], 2, 2, 5) is True
    assert is_open([
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 1, 1, 1, 1, 1, 0, 0],
        [0, 0, 1, 1, 1, 1, 1, 0, 0],
        [0, 0, 1, 1, 1, 1, 1, 0, 0],
        [0, 0, 1, 1, 1, 1, 1, 0, 0],
        [0, 0, 1, 1, 1, 1, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
    ], 2, 2, 5) is False
  • 인자로 주어지는 값은 확장된 자물쇠, 시작 행, 시작 열, 확장 전 자물쇠의 가로(또는 세로) 길이 이다.
  • 확장된 자물쇠의 가운데에 있는 실제 자물쇠 값이 모두 1이라면 True를 반환한다.
  • 만약 0이나 2가 있다면 자물쇠는 열리지 않은 것이므로 False를 반환한다.

키 회전하기

def rotate(array):
    rotated = [[0] * len(array) for _ in range(len(array))]
    k = len(array) - 1
    for i in range(len(array)):
        for j in range(len(array)):
            rotated[j][k] = array[i][j]
        k -= 1

    return rotated
    
def test_rotate():
    assert rotate([
        [1, 1, 1],
        [1, 1, 0],
        [1, 0, 1],
    ]) == [
               [1, 1, 1],
               [0, 1, 1],
               [1, 0, 1],
           ]

    assert rotate([
        [1, 1, 1],
        [0, 1, 1],
        [1, 0, 1],
    ]) == [
               [1, 0, 1],
               [0, 1, 1],
               [1, 1, 1],
           ]
    assert rotate([
        [1, 0, 1],
        [0, 1, 1],
        [1, 1, 1],
    ]) == [
               [1, 0, 1],
               [1, 1, 0],
               [1, 1, 1],
           ]
    assert rotate([
        [1, 0, 1],
        [1, 1, 0],
        [1, 1, 1],
    ]) == [
               [1, 1, 1],
               [1, 1, 0],
               [1, 0, 1],
           ]
    assert rotate([
        [1, 0, 1, 1],
        [1, 1, 0, 1],
        [1, 1, 1, 0],
        [0, 1, 1, 0],
    ]) == [
               [0, 1, 1, 1],
               [1, 1, 1, 0],
               [1, 1, 0, 1],
               [0, 0, 1, 1],
           ]
    assert rotate([
        [1, 0, 1, 1, 1],
        [1, 1, 0, 1, 0],
        [1, 1, 1, 0, 1],
        [0, 1, 1, 0, 0],
        [0, 1, 1, 1, 1],
    ]) == [
               [0, 0, 1, 1, 1],
               [1, 1, 1, 1, 0],
               [1, 1, 1, 0, 1],
               [1, 0, 0, 1, 1],
               [1, 0, 1, 0, 1],
           ]
  • 정사각형 2차원 배열을 시계 방향으로 회전하는 함수이다.
  • 만약 3 X 3 배열을 시계 방향으로 회전하기 위해 좌표를 적어보면 아래와 같고, 이를 반복문으로
    작성하였다.
[0][0] -> [0][2] / [1][0] -> [0][1] / [2][0] -> [0][0]
[0][1] -> [1][2] / [1][1] -> [1][1] / [2][1] -> [1][0]
[0][2] -> [2][2] / [1][2] -> [2][1] / [2][2] -> [2][0]

최종 solution 함수

import copy


def solution(key, lock):
    lock_length, key_length = len(lock), len(key)
    expanded_lock = lock_expansion(lock, lock_length, key_length)
    for _ in range(4):
        for y in range(lock_length + key_length - 1):
            for x in range(lock_length + key_length - 1):
                if is_open(unlock(key, y, x, copy.deepcopy(expanded_lock)),
                           key_length - 1, key_length - 1, lock_length):
                    return True
        key = rotate(key)
    return False

def test_solution():
    assert solution([[0, 0, 0], [1, 0, 0], [0, 1, 1]],
                    [[1, 1, 1], [1, 1, 0], [1, 0, 1]]) is True
    assert solution([[0, 1, 0], [1, 1, 0], [1, 0, 1]],
                    [[1, 0, 1, 1, 1], [0, 0, 1, 1, 1], [0, 1, 0, 1, 1],
                     [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]]) is True
  • for _ in range(4) 는 4번의 회전을 위해 사용한다.
  • (0, 0) 부터 자물쇠의 오른쪽 맨 아래 좌표까지 대입한다.
  • 위에 설명한 함수대로 결과를 True또는 False로 반환한다.

고찰

문제를 구현하면서 가장 애먹은 부분은 key의 길이와 lock의 길이를 인자로 전달하는 부분에서 발생하였다. 이를 잘못 전달하여 제대로 구현했음에도 불구하고 정답을 도출하지 못하고 시간을 허비했다.😭

예를 들어 is_open 함수에 인자로 전달해야 하는 sysxkey 배열의 길이 - 1lock 배열의 길이 - 1 를 전달하고, 마지막 인자는 key의 길이를 전달하여 제대로 된 검사를 수행하지 못했다.

즉, 다음과 같은 테스트 케이스가 있다고 해보자.

 is_open([[0, 0, 0, 0, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 0, 0, 0, 0, 0],
         [0, 0, 1, 1, 1, 1, 1, 0, 0],
         [0, 0, 1, 1, 1, 1, 1, 0, 0],
         [0, 0, 1, 1, 1, 1, 1, 0, 0],
         [0, 0, 1, 1, 1, 1, 1, 0, 0],
         [0, 0, 1, 1, 1, 1, 0(*), 0, 0],
         [0, 0, 0, 0, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 0, 0, 0, 0, 0],
    	 ], 2, 2, 5) is False

위의 테스트 케이스는 (*) 부분에 의해 열리지 않는다.
이러한 테스트 케이스에 인자로sy 값을 key_length - 1로 전달하고, sx 값에 lock_length - 1을 전달하면 검사하는 가로, 세로의 길이가 달라 정확한 lock 전체를 검사하지 못한다. 따라서 True가 나올 수 있다는 것이다.

따라서 정확한 변수명을 사용하여 인자로 전달하고, 예외가 될 수 있는 테스트 케이스 작성이 매우 중요함을 알 수 있었다.

문제 링크 : 자물쇠와 열쇠

0개의 댓글