이 문제는 다차원 배열을 이용해 전체 경우를 탐색하여 해당 자물쇠를 열쇠로 열 수 있는지 검사하는 문제이다. 문제에서 주어지는 N과 M의 제한이 크지 않아 모든 경우를 탐색해도 시간 초과가 발생하지 않을 것이라 생각했다.
내가 푼 방식은 아래와 같다.
(0,0)
부터 key
의 원소들을 key
의 크기만큼 lock
의 원소에 하나씩 더해준다.key
를 대입했을 때 자물쇠가 모두 1로 채워져 있다면 True
를 반환한다.0(자물쇠의 모든 홈이 채워지지 않음)
이나 2(자물쇠와 열쇠의 돌기가 만남)
라면 이는 열리지 않는 것이므로 False
를 반환한다.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
확장된 자물쇠, 시작 행, 시작 열, 확장 전 자물쇠의 가로(또는 세로) 길이
이다.True
를 반환한다.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],
]
[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]
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
함수에 인자로 전달해야 하는 sy
와 sx
에 key 배열의 길이 - 1
과 lock 배열의 길이 - 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
가 나올 수 있다는 것이다.
따라서 정확한 변수명을 사용하여 인자로 전달하고, 예외가 될 수 있는 테스트 케이스 작성이 매우 중요함을 알 수 있었다.
문제 링크 : 자물쇠와 열쇠