문제
: m * m 크기의 key와 n * n 크기의 lock 존재.
key는 90도씩 회전 가능
각각 홈 0, 돌기 1.
key의 돌기가 lock의 홈에 만나고, lock에 빈 홈이 없으며, 서로의 돌기가 만나지 않았을 때 자물쇠가 열림
주어진 key로 lock이 열리면 true, 열리지 않으면 false 반환
-
테스트 케이스
key = [[0, 0, 0], [1, 0, 0], [0, 1, 1]]
lock = [[1, 1, 1], [1, 1, 0], [1, 0, 1]] -
답
true
나의 풀이
1. 재귀 함수: 성공!!
def key_lock(x, y, rotation, key, lock):
# 원본, 90도, 180도, 270도 회전
key_list = [key,
list(map(list, zip(*reversed(key)))),
list(map(lambda x: list(reversed(x)), reversed(key))),
list(reversed(list(map(list, zip(*key)))))]
m, n = len(key), len(lock)
lock_extend = [[0] * 3 * n for _ in range(3 * n)]
# lock_extend 가운데 lock을 위치 시킨다
for i in range(n):
for j in range(n):
lock_extend[i + n][j + n] = lock[i][j]
# lock_extend와 key를 겹쳐봄
for i in range(m):
for j in range(m):
lock_extend[i + x][j + y] += key_list[rotation][i][j]
# lock_extend에 속한 lock list
lock_list = list(map(lambda x: x[n:2 * n], lock_extend[n:2 * n]))
# lock_list에 1만 남아있다면, True 반환
if set(sum(lock_list, [])) == {1}:
return 'True'
else:
# key가 lock_list를 다 훑어봤다면
if (x, y) == (2 * n - 1, 2 * n - 1):
# 270도까지 회전 했다면
if rotation == 3:
return 'False'
else: # key를 회전
x, y = 1, 1
return key_lock(x, y, rotation + 1, key, lock)
# key가 lock_list와 겹쳐진 마지막 열이라면, 다음 행으로 이동
elif x < 2 * n - 1 and y == 2 * n - 1:
return key_lock(x + 1, 0, rotation, key, lock)
# 다음 열로 이동(=한 칸 오른쪽으로 이동동)
else:
return key_lock(x, y + 1, rotation, key, lock)
key_lock(1, 1, 0, key, lock): lock_list = list(map(lambda x: x[n:2 * n], lock_extend[n:2 * n]))의 위치가 자꾸만 틀린 답을 내게 했던 것!
-
기존
: lock_extend를 설정 한 후, lock_list를 설정하고, lock_extend와 key를 겹쳐봄
: lock_list를 설정한 이후에 lock_extend와 key를 겹쳐보았기 때문에 lock_list의 값이 변하지 않았던 것! -
수정
: lock_extend를 설정 한 후, lock_extend와 key를 겹쳐보고, lock_list를 설정!
프로그래머스 제출 내역
import sys
sys.setrecursionlimit(100000) #재귀의 한도를 100000까지 풀어준다.
def key_lock(x, y, rotation, key, lock):
# 원본, 90도, 180도, 270도 회전
key_list = [key,
list(map(list, zip(*reversed(key)))),
list(map(lambda x: list(reversed(x)), reversed(key))),
list(reversed(list(map(list, zip(*key)))))]
m, n = len(key), len(lock)
lock_extend = [[0] * 3 * n for _ in range(3 * n)]
# lock_extend 가운데 lock을 위치 시킨다
for i in range(n):
for j in range(n):
lock_extend[i + n][j + n] = lock[i][j]
# lock_extend와 key를 겹쳐봄
for i in range(m):
for j in range(m):
lock_extend[i + x][j + y] += key_list[rotation][i][j]
# lock_extend에 속한 lock list
lock_list = list(map(lambda x: x[n:2 * n], lock_extend[n:2 * n]))
# lock_list에 1만 남아있다면, True 반환
if set(sum(lock_list, [])) == {1}:
return True
else:
# key가 lock_list를 다 훑어봤다면
if (x, y) == (2 * n - 1, 2 * n - 1):
# 270도까지 회전 했다면
if rotation == 3:
return False
else: # key를 회전
x, y = 1, 1
return key_lock(x, y, rotation + 1, key, lock)
# key가 lock_list와 겹쳐진 마지막 열이라면, 다음 행으로 이동
elif x < 2 * n - 1 and y == 2 * n - 1:
return key_lock(x + 1, 0, rotation, key, lock)
else: # 다음 열로 이동(=한 칸 오른쪽으로 이동)
return key_lock(x, y + 1, rotation, key, lock)
# 프로그래머스 문제에서는 solution 함수만 있길래...
def solution(key, lock):
answer = key_lock(1, 1, 0, key, lock)
return answer- 어어엄청 높은 시간 복잡도와 공간 복잡도;;
테스트 11 〉 통과 (1526.93ms, 268MB)
: 처음에는 런타임 에러가 뜨는것이었다!
: 이유를 찾아보니 여러가지가 있는데.. 아무래도 재귀 함수를 너무 많이 호출 해서 그런 것 같단 말이지..?
import sys
sys.setrecursionlimit(100000): 이걸 추가하니까 해결! 재귀의 한도를 10000까지 풀어준다!
- numpy 없이 푸는 습관을 들이자! 물론 난 numpy 사용 할 줄 몰라서 안씀 ^^
: numpy는 보통 코딩테스트에서 기본 패키지로 인정하지 않습니다..
2. 5중 for문(반복문) 사용: 성공
# key_list와 lock_extend 확대공간을 만들고, 그 공간에 key 겹쳐보기
# 반환: lock_extend 공간에 key 겹쳤을 때 lock의 상태
def key_lock(x, y, rotation, key, lock):
# 원본, 90도, 180도, 270도 회전
key_list = [key,
list(map(list, zip(*reversed(key)))),
list(map(lambda x: list(reversed(x)), reversed(key))),
list(reversed(list(map(list, zip(*key)))))]
m, n = len(key), len(lock)
# lock 길이의 3배 크기의 공간 생성
lock_extend = [[0] * 3 * n for _ in range(3 * n)]
# lock_extend 가운데 lock을 위치 시킨다
for i in range(n):
for j in range(n):
lock_extend[i + n][j + n] = lock[i][j]
# lock_extend와 key를 겹쳐보기
for i in range(m):
for j in range(m):
lock_extend[i + x][j + y] += key_list[rotation][i][j]
# lock_extend에 속한 lock list
return list(map(lambda x: x[n:2 * n], lock_extend[n:2 * n]))
# key를 회전시키며 lock이 전부 1인지(=key와 lock이 꼭 들어맞는지) 확인해서
# true or false 반환하기
def solution(key, lock):
m, n = len(key), len(lock)
for r in range(4): # rotation: 0, 90, 180, 270도 회전
for a in range(1, 2 * n):
for b in range(1, 2 * n):
lock_center = key_lock(a, b, r, key, lock)
# lock_list에 1만 남아있다면, True 반환
if set(sum(lock_center, [])) == {1}:
return True
# 270도까지 회전하고,
# lock_extend를 다 훑었는데도 key와 lock이 안 맞는다면,
# False 반환
if set(sum(lock_center, [])) != {1}:
return False- 상대적으로 높은 시간 복잡도와 공간 복잡도
테스트 11 〉 통과 (691.38ms, 10.3MB)
- 함수를 두개로 쪼갬
- 기본적인 key list와 lock 공간을 만들고, key를 갖다 대봄
- key를 회전시키면서 key와 lock이 잘 맞물리면 true, 270도 까지 회전했는데도 맞물리지 않으면 false 출력
- 재귀 함수를 사용 했을 때보다 더 적은 시간 복잡도와 공간 복잡도를 보였다! 역시.. 재귀는 자제해야하나..?
3. 4중 for문: 성공
def solution(key, lock):
# 0도, 90도, 180도, 270도 key들
keys = [
key,
list(map(list, zip(*reversed(key)))),
list(map(lambda x: list(reversed(x)), reversed(key))),
list(reversed(list(map(list, zip(*key)))))
]
n, m = len(lock), len(key) # lock: n * n, key: m * m
# 상하좌우 3배(=9배) 넓어진 locks
locks = [[0] * (3 * n) for _ in range(3 * n)]
for i in range(n, 2 * n): # locks의 중앙에 lock을 위치시킴
locks[i][n:2 * n] = lock[i - n]
now_lock = [x[:] for x in locks] # 원본 보존용으로 locks 깊은복사
for turn in range(4):
now_key = keys[turn] # 현재 key는 몇 도?
# x와 y를 이동해가며 key로 lock이 열리는지 확인하기
for x in range(1, 2 * n):
for y in range(1, 2 * n):
for a in range(x, x + m): # 현재 위치의 key와 lock을 맞춰보기
now_lock[a][y:y + m] = map(lambda a, b: a + b, now_lock[a][y:y + m], now_key[a - x])
# lock이 key로 열린다면(lock의 홈 + key의 돌기 = 1)
if set(sum(map(lambda x: x[n:2 * n], now_lock[n:2 * n]), [])) == {1}:
return True
now_lock = [x[:] for x in locks] # now_lock 초기화
return False- 4가지 포인트
-
now_lock = [x[:] for x in locks]
: 원본 보존용으로 locks 깊은복사
: 깊은 복사를 할 때, deepcopy보다 이런 slicing이 더 빠름! 특히 2중 list때 주의하기~ -
locks[i][n:2 * n] = lock[i - n]
: locks의 중앙에 lock을 위치시킴 -
now_lock[a][y:y + m] = map(lambda a, b: a + b, now_lock[a][y:y + m], now_key[a - x])
: 현재 위치의 key와 lock을 맞춰보기 -
if set(sum(map(lambda x: x[n:2 * n], now_lock[n:2 * n]), [])) == {1}:
: 이건 저번 5중 for문과 거의 유사하긴 함
- 가장 높은 시간 복잡도의 케이스
:테스트 27 〉 통과 (378.25ms, 10.2MB)
다시풀기: 흠
def make_locks(n, lock, locks): # locks_space 중앙에 lock 위치시키기
for i in range(n, n * 2):
locks[i][i:i+n] = lock[i-n]
return locks
def solution(key, lock):
m, n = len(key), len(lock)
# 0도, 90도, 180도, 270도
keys = [
key,
list(map(list, zip(*reversed(key)))),
list(map(lambda x: list(reversed(x)), reversed(key))),
list(reversed(list(map(list, zip(*key)))))
]
len_2, len_3 = n * 2, n * 3
# key가 탐색할 공간 만들기(lock의 가로세로 3배 넓이)
locks = [[0] * (len_3) for _ in range(len_3)]
locks_lock = make_locks(n, lock, locks)
stop_true = False
for now_key in keys: # key를 돌려가며
for x in range(1, len_2):
for y in range(1, len_2):
for now in range(x, x + m): # 현재 위치의 key와 lock을 맞춰보기
locks[now][y:y + m] = map(lambda a, b: a + b, locks[now][y:y + m], locks[now - x])
# lock이 key로 열린다면(lock의 홈 + key의 돌기 = 1)
if set(sum(map(lambda x: x[n:2 * n], now_lock[n:2 * n]), [])) == {1}:
return True
now_lock = [x[:] for x in locks] # now_lock 초기화
return False
내 인생의 주연