[프로그래머스] 자물쇠와 열쇠
로직은 이렇게 구성했습니다.
만약 이렇게 key의 크기가 3*3이고 lock의 사이즈가 4일때
(빨간 곳은 겹치는 배열) 이러한 배열을 만드시는 분들이 많더라구요.
그런데 어차피 탐색을 할 때 기준점을 키의 왼쪽 위 즉
이렇게 잡는다면 만든 큰 배열에서 기준점이 들어갈 수 있는 곳은 배열의 크기보다 꽤나 작습니다.
연두색 부분은 검사를 할 필요도 없는 부분입니다. 기준점이 연두색 부분에 있으면 모든 값이 자물쇠 바깥의 값들이니까요. 이렇게 한다면 배열의 크기를 (자물쇠의 크기+(열쇠의 크기-1)*2)^2 에서 (자물쇠의 크기+열쇠의 크기-1)^2로 줄일 수 있습니다. 짠돌이 호석의 경우 무조건 정사각형도 아니고 크기도 어떤것이 크다! 라고 하기 애매한 것들도 많아서 구현에 실패했었지만 이 문제는 가능할 것 같아서 이렇게 짜주었습니다.
결론적으로 저 노란 부분의 배열만큼의 배열을 만들어주었습니다.
해당 크기의 배열을 만들 빨간색 부분에는 lock의 값들이 위치하게 해주었습니다. 그리고 마찬가지로 탐색을 진행할 때 노란 부분의 위치는 탐색을 진행할 필요가 없습니다. 마찬가지로 저 부분은 자물쇠의 밖이니까요!
for i in range(mx_len):
for j in range(mx_len):
correct=0
unable=False
for ii in range(l1):
nowy=i+ii
if l1-2<nowy<mx_len:
for jj in range(l1):
nowx=j+jj
if l1-2<nowx<mx_len:
if rotated_key[ii][jj]==1 and bigmap[nowy][nowx]==0:
correct+=1
elif rotated_key[ii][jj]&bigmap[nowy][nowx]==1:
unable=True
break
if unable:
break
if unable:
continue
if correct==lock_hole:
return True맞은 것을 표현할 변수 correct와 조건에 맞지 않으면 다중 반복문을 탈출할 때 필요한 unable을 선언해준뒤 탐색을 진행하였습니다.
탐색 방법은 다음과 같습니다.
해당 길이 범위 내의 좌표를 정한 뒤 key의 값만큼 오른쪽 아래 방향으로 탐색해주었습니다
이때 탐색하는 부분이 빨간색 배열의 바깥이 아닐때만 비교해주었습니다.
아래는 코드 입니다.
def make_big_table(arr1,arr2): # 큰 배열을 만드는 함수
l1=len(arr1)-1
l2=len(arr2)
n_arr=[[0 for i in range(l1+l2)] for i in range(l1)] # 큰 배열의 윗 부분을 미리 만들어놓기
for i in range(l2):
n_arr.append([0 for i in range(l1)]+arr2[i]) # key의 크기-1 만큼 [0,0,0...]+ lock의 한 줄
return n_arr,len(n_arr) # 만든 큰 배열과 큰 배열의 한 변의 길이를 리턴
def rotate(arr1): # 회전시킨 4개의 모양을 리턴해주느 함수
l1=len(arr1)
rotated=[arr1,[],[],[]]
for _ in range(3):
at_rotated=[[0 for i in range(l1)]for i in range(l1)]
for i in range(l1):
for j in range(l1):
at_rotated[~j][i]=rotated[_][i][j]
rotated[_+1]=at_rotated
return rotated
def solution(key,lock):
l1=len(key)
l2=len(lock)
bigmap,mx_len=make_big_table(key,lock) # 큰 배열과 최대 길이 저장
rotated_keys=rotate(key) # 회전한 4개의 모습 저장
lock_hole=0 # 자물쇠의 구멍 개수
# 2중 for문으로 자물쇠의 구멍 개수를 구해줌
for i in range(l2):
for j in range(l2):
if lock[i][j]==0:
lock_hole+=1
for rotated_key in rotated_keys: # 가장 바깥에 회전한 열쇠들
for i in range(mx_len): # 큰 배열내의 y
for j in range(mx_len): # 큰 배열내의 x
correct=0 # 채운 구멍의 갯수
unable=False # 2중 for문을 탈출하고 구멍 갯수 비교를 스킵시켜줄 변수
for ii in range(l1): # key값만큼 탐색
nowy=i+ii
if l1-2<nowy<mx_len: # lock의 범위 내에 속한다면
for jj in range(l1):
nowx=j+jj
if l1-2<nowx<mx_len: # lock의 범위 내에 속한다면
if rotated_key[ii][jj]==1 and bigmap[nowy][nowx]==0: # 만약 key에서 저 좌표의 값이 0이고, 큰 배열의 좌표의 값은 0이라면
correct+=1 # 하나 채워준다.
elif rotated_key[ii][jj]&bigmap[nowy][nowx]==1: # 만약 &연산 결과가 1이라면 (둘다 1이라면)
unable=True # 어떻게 해도 불가능이다
break
if unable:
break
if unable:
continue
if correct==lock_hole: #만약 구멍의 개수와 채운 개수가 같다면
return True
return False