[programmers 60059] 2020 공채 3번 자물쇠와열쇠
문제
접근법
M,N이 20이 이하이므로 완전 탐색 쓰기!
전체 흐름
for 90도씩 회전:
# key 반시계방향으로 돌리기
for key 한칸씩 이동하며 자물쇠 홈 채우기:
# 딱 맞으면 True 리턴
# 딱 맞는 경우가 없으면 False 리턴
코드
def solution(key, lock):
M,N = len(key),len(lock) # 3<=M<=N<=20
# lock길이의 3배인 board를 만들어 가운데를 lock값으로 초기화
board = [ [0]*3*N for _ in range(3*N) ]
for i in range(N):
for j in range(N):
board[N+i][N+j]=lock[i][j]
newkey = [ [0]*M for _ in range(M)]
# key 90도씩 회전시키고 모든 경우에 대하여 홈 채우기
for dir in range(4):
# key 반시계방향으로 돌리기
for i in range(M):
for j in range(M):
newkey[i][j] = key[j][M-1-i]
### 한칸씩 이동하며 홈 채우기
for X in range(N-M+1,2*N): #N-M+1부터 2*N-1까지
for Y in range(N-M+1,2*N):
newboard = [ board[i][:] for i in range(3*N) ] # 처음 board 값 복사
# 자물쇠에 열쇠 끼워넣기
for i in range(M):
for j in range(M):
newboard[X+i][Y+j] += newkey[i][j]
# 딱 맞는지 체크
check = 0
for i in range(N,2*N):
for j in range(N,2*N):
if newboard[i][j]==1:
check += 1
if check==N**2:
return True
key = [ newkey[i][:] for i in range(M) ] # key에 현재 newkey값 복사해야 이따 재활용할 수 있음
return False
실수한 점
'딱 맞는지 체크'하는 부분을 다음과 같이 잘못 짰다.
# 딱 맞는지 체크
if sum(map(sum,newlock))==(N**2):
return True
이 코드는 자물쇠와 열쇠가 모두 돌기인 경우(newboard[i][j]==2
)를 고려하지 못한 코드다
따라서 다음과 같이 바꿔주었다
# 딱 맞는지 체크
check = 0
for i in range(N,2*N):
for j in range(N,2*N):
# 정확히 1일 때만
if newboard[i][j]==1:
check += 1
if check==N**2:
return True
결과
Author And Source
이 문제에 관하여([programmers 60059] 2020 공채 3번 자물쇠와열쇠), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@savannah030/programmers-60059-2020-공채-3번-자물쇠와열쇠저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)