title: "[프로그래머스] 자물쇠와 열쇠 Python 파이썬 해설 (Level 3) - 이도훈"
cleanUrl: "programmers/60059"
description: "프로그래머스 Level 3 문제 [자물쇠와 열쇠]의 풀이를 정리합니다."
import copy
def solution(key, lock):
# 자물쇠의 크기 N, 열쇠의 크기 M
# 자물쇠를 양 옆으로 M-1만큼 확장하고, 확장된 칸은 모두 1로 채웁니다.
# 이러면 홈 부분의 좌표는 (r + (M-1), c + (M-1))입니다.
# 열쇠를 4가지로 회전한 버전을 sliding window 방식으로
# 자물쇠에 대보고, 자물쇠 범위 내에서 XOR한 값들이 모두 1이 아니면
# false를 리턴합니다.
N, M = len(lock), len(key)
# 우선 홈 부분의 좌표들을 저장해둡니다.
rooms = []
for r, row in enumerate(lock):
for c, num in enumerate(row):
if num == 0:
rooms.append( (r + (M-1), c + (M-1)) )
# 자물쇠를 확장합니다.
newlock = [ [1] * (2*M - 2 + N) for _ in range(M-1) ]
for r, row in enumerate(lock):
newlock += [[1] * (M-1) + row + [1] * (M-1)]
newlock += [ [1] * (2*M - 2 + N) for _ in range(M-1) ]
# 4가지 버전의, 회전한 열쇠들을 마련합니다.
# 그대로
turn0 = key
# 시계방향 90도
turn90 = copy.deepcopy(key)
for r, row in enumerate(key):
for c, num in enumerate(row):
turn90[c][M-1-r] = num
# 180도
turn180 = copy.deepcopy(key)
for r, row in enumerate(key):
for c, num in enumerate(row):
turn180[M-1-r][M-1-c] = num
# 반시계방향 90도
turn270 = copy.deepcopy(key)
for r, row in enumerate(key):
for c, num in enumerate(row):
turn270[M-1-c][r] = num
# 키들을 대봅니다.
keys = [turn0, turn90, turn180, turn270]
for k in keys:
for r in range(N + M + 1):
for c in range(N + M + 1):
# 열쇠의 왼쪽 위 부분이 (r, c)입니다.
# 즉 열쇠가 커버하는 부분은 (r, c) ~ (r + (M-1), c + (M-1))
# 까지입니다.
l = copy.deepcopy(newlock)
# 열쇠가 홈을 커버하지 못하면 검사해볼 필요가 없습니다.
skip = False
for roomr, roomc in rooms:
if not (r <= roomr < r+M and c <= roomc < c+M):
skip = True
break
if skip:
continue
found = True
for r1 in range( max(r, M-1), min(M+N-1, r+M) ):
for c1 in range( max(c, M-1), min(M+N-1, c+M) ):
if k[r1-r][c1-c] ^ l[r1][c1] == 0:
found = False
break
if not found:
break
if found:
return True
return False
프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges