1. 문제
- 프로그래머스 문제
- N x N 자물쇠가 있고, M x M 의 열쇠가 있다.
- 좌물쇠도 0, 1, 열쇠도 0, 1로 이루어져 있다.
- 열쇠는 회전과 수평, 수직 이동이 가능하다.
- 회전, 수평, 수직 이동으로 좌물쇠의 홈에, 열쇠의 돌기만 맞추어야 한다.
- 돌기와 돌기가 맞으면 안된다.
- 자물쇠를 열수 있으면 True, 열수 없으면 False 를 반환하는 프로그램을 만들라.
제한사항 및 입출력 예
2. 아이디어
- 효율성을 따지지 않기 때문에 완전탐색 방법을 사용한다.
- 자물쇠 2차원 리스트를 3배 크기로 크게 만들어서 열쇠를 한칸씩 오른쪽 아래로 이동시키면서 차례차례 열쇠가 맞는지 확인한다.
- 90도 회전, 열쇠가 맞았는지 확인하는 함수를 만든다.
- 열쇠 2차원 리스트를 왼쪽 최상단에서, 오른쪽 최하단까지 한칸씩 이동시키면서, 자물쇠에 더한다.
- 자물쇠 리스트의 모든 부분이 1인지 확인한다.
- 아니면, 다시 열쇠를 제거한다. (더했던 것을 다시 뺀다.)
3. 예제코드
# 2차원 리스트 회전
def rotate_a_matrix_by_90_degree(a):
n = len(a) # 행 길이
m = len(a[0]) # 열 길이
result = [[0] * n for _ in range(m)] # 결과 리스트
for i in range(n): # 세로
for j in range(m): # 가로
result[j][n - i - 1] = a[i][j]
# 가로 정보는 그대로 세로로 가져오고, 세로정보는 행의 길이에서 행의 정보를 빼고 1을 더빼서 가져온다.
return result
# 자물쇠의 중간 부분이 모두 1인지 확인
def check(new_lock):
lock_length = len(new_lock)//3 # 자물쇠를 세배 크게 만들었으니까 , 다시 줄여서
for i in range(lock_length, lock_length *2): # 중심부를 탐색
for j in range(lock_length, lock_length *2):
if new_lock[i][j] != 1: # 1인지 확인 , 아니면, False
return False
return True # 모두 탐색했는데, 문제없으면 True
def solution(key, lock):
n = len(lock)
m = len(key)
# 자물쇠의 크기를 기존의 3배로 변환
new_lock = [[0]*(n*3) for _ in range(n*3)]
# 새로운 자물쇠의 중앙 부분에 기존의 자물쇠 넣기
for i in range(n):
for j in range(n):
new_lock[i+n][j+n] = lock[i][j]
# 4가지 방향에 대해서 확인
for rotation in range(4):
key = rotate_a_matrix_by_90_degree(key) # 열쇠 회전
for x in range(n*2):
for y in range(n*2): # 자물쇠에 열쇠를 끼워 넣기
for i in range(m):
for j in range(m):
new_lock[x+i][y+j] += key[i][j]
# 새로운 자물쇠에 열쇠가 정확히 들어맞는지 검사
if check(new_lock) == True:
return True
# 자물쇠에서 열쇠를 다시 빼기
for i in range(m):
for j in range(m):
new_lock[x+i][y+j] -= key[i][j]
return False # 모두 탐색했는데, 열쇠가 안맞으면 느낀점
- 2차원 리스트를 자다가 바로 일어나서도 가지고 놀줄 알아야 한다.
참고
- 이것이 취업을 위한 코딩 테스트다. with 파이썬
성장하는 데이터 분석가