[이것이 파이썬 코딩테스트다 - 구현] 자물쇠와 열쇠
고고학자인 "튜브"는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다.
잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다.
자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있습니다. 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다. 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않지만, 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다. 또한 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있습니다.
열쇠를 나타내는 2차원 배열 key와 자물쇠를 나타내는 2차원 배열 lock이 매개변수로 주어질 때, 열쇠로 자물쇠를 열수 있으면 true를, 열 수 없으면 false를 return 하도록 solution 함수를 완성해주세요.
제한사항
- key는 M x M(3 ≤ M ≤ 20, M은 자연수)크기 2차원 배열입니다.
- lock은 N x N(3 ≤ N ≤ 20, N은 자연수)크기 2차원 배열입니다.
- M은 항상 N 이하입니다.
- key와 lock의 원소는 0 또는 1로 이루어져 있습니다.
- 0은 홈 부분, 1은 돌기 부분을 나타냅니다.
입출력 예
keylockresult
| [[0, 0, 0], [1, 0, 0], [0, 1, 1]] | [[1, 1, 1], [1, 1, 0], [1, 0, 1]] | true |
입출력 예에 대한 설명
key를 시계 방향으로 90도 회전하고, 오른쪽으로 한 칸, 아래로 한 칸 이동하면 lock의 홈 부분을 정확히 모두 채울 수 있습니다.
import copy
# 시계방향으로 90도 돌리는 함수
def rotate_90_degree(key):
result = copy.deepcopy(key)
size = len(result)
for i in range(size):
for j in range(size):
result[i][j] = key[j][size-1-i]
return result
def solution(key, lock):
answer = False
m = len(key)
n = len(lock)
# key를 4번 순회
for i in range(4):
key = copy.deepcopy(key)
# key를 시계방향으로 90도 돌리기
r_key = rotate_90_degree(key)
# 매칭 시작
for start_row in range((m-1)//2+n):
for start_col in range((m-1)//2+n):
# start_row, start_col이 하나의 경우의 수
n_lock = copy.deepcopy(lock)
for r_inc in range(m):
for c_inc in range(m):
nx = start_row + r_inc
ny = start_col + c_inc
if nx >= (m-1)//2 and nx < n + (m-1)//2 and ny >= (m-1)//2 and ny < n + (m-1)//2:
if r_key[r_inc][c_inc] == 1 and n_lock[nx-(m-1)//2][ny-(m-1)//2] == 0:
n_lock[nx-(m-1)//2][ny-(m-1)//2] = 1
count = 0
for a in range(n):
count += sum(n_lock[a])
if count == n*n:
answer = True
break
return answer
착안한 아이디어:
시계방향 90도 회전 -> sliding 윈도우 기법 적용 -> 그래서 자물쇠 위치에 남는 애들만 건드리는 전략
=> 정확도 점수: 52% ㅠㅠㅠ
틀린 이유를 곰곰히 생각해보니, sliding window 기법을 적용할 때, 전체 행렬 사이즈를 m(lock) + 2*n(key) - 2로 뒀어야 했는데, m+n -1로 두었다.
알고리즘을 떠올려도 전체 사이즈를 헷갈려서 문제를 틀리지 않았나 싶다.
이렇게 다시 바꾸고 다시 돌아와서 풀어보자.
--> 후 해결했다 !!
-> 레전드 인점: 시계방향으로 90도라고 해놓고 반시계방향으로 90도 돌아가는 내 코드... 진짜 실화냐???
-> 그리고, deepcopy를 쓰면서 n번 돌아가는 코드를 구현 못했었다...! 이런 부분은 잊지말고 연쇄적으로 돌릴 수 있도록 코드 구성해야겠다 !! (실제 시험장에서 print로 디버깅이 될란지 모르겠네 ㅠㅠ)
-> 오른쪽 끝 값 주의 -> 인덱싱으로 접근하다보니 (m+n-1)번째 인덱스에서 접근하는 것에 어려움을 겪었다...
=> 아래에 수정한 코드를 올려두겠음 !!
import copy
# 반시계방향으로 90도 돌리는 함수
def rotate_90_degree(key,index):
result = copy.deepcopy(key)
size = len(result)
for k in range(index):
new_result = copy.deepcopy(result)
for i in range(size):
for j in range(size):
new_result[i][j] = result[j][size-1-i]
result = new_result
return result
def solution(key, lock):
answer = False
m = len(key)
n = len(lock)
# key를 4번 순회
for i in range(4):
key = copy.deepcopy(key)
# key를 반,,,,시계방향으로 90도 돌리기
r_key = rotate_90_degree(key,i+1)
# print(r_key)
# 매칭 시작
for start_row in range(m+n):
for start_col in range(m+n):
# start_row, start_col이 하나의 경우의 수
n_lock = copy.deepcopy(lock)
for r_inc in range(m):
for c_inc in range(m):
nx = start_row + r_inc
ny = start_col + c_inc
if nx >= m and nx < m+n and ny >= m and ny < m+n:
if r_key[r_inc][c_inc] == 1 and n_lock[nx-(m)][ny-(m)] == 1:
n_lock[nx-(m)][ny-(m)] = -99999
if r_key[r_inc][c_inc] == 1 and n_lock[nx-(m)][ny-(m)] == 0:
n_lock[nx-(m)][ny-(m)] = 1
count = 0
for a in range(n):
count += sum(n_lock[a])
if count == n*n:
answer = True
break
return answer
그래도 죽이되든 밥이되든 내가 짠 코드로 테케 올솔하는 거 보면 마음이 뿌듯하고,,, 그렇다,,, 포기하려고 했는데 포기 안한 내 자신 칭찬혀,,, (근데 다 짜고 인스타봐야지 하다가 짜증나서 인스타보고 네이버 블로그 보고,,, 그러면 못 써 에잉 쯧쯧 !!)
동빈나씨 풀이 원하는 분들도 있을 것 같아 추가적으로 공유합니다...!
-> 완전 나이브한 방식인데, 이렇게 짜는 게 훨 나을 것 같다는 생각이 듦
-> 슬라이딩 윈도우 적용하되, 그냥 자물쇠 크기의 *3의 빈 행렬을 만들어서 가운데에 lock넣는 것.
-> 나는 *3이 아니라 m+n-1크기의 빈 행렬에다가 넣으려다가 실패했는데, 이런 거 보면 단순하고, 빠른 방식으로 누가 더 잘 구현하느냐 싸움인지를 알 수 있었던 것 같다 !!
-> 시작 인덱스, 끝 인덱스에 대한 구분이 명확하다 -> 이렇게 풀면 !!
def rotate_a_matrix_by_90_degrees(a):
# get the length of row
n = len(a)
# get the length of col
m = len(a[0])
result = [[0] * n for _ in range(m)]
for i in range(n):
for j in range(m):
# i번째 row -> n-1-i번쨰 col
# j번째 col -> j번쨰 col
result[j][n - 1 - i] = a[i][j]
return result
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:
return False
return True
def solution(key,lock):
n = len(lock)
m = len(key)
# 자물쇠 크기 기존의 3배로 변환
new_lock = [[0] * 3 *n for _ in range(3*n)]
# 새로운 자물쇠의 중앙 부분에 기존의 자물쇠 넣기
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_degrees(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
중요한 것 !
90도 회전하는 함수 모듈로 저장해두기 !!
def rotate_90_degree_colockwise(array):
# 행
row = len(array)
#열
col = len(array[0])
result = [[0] * col for _ in range(row)]
for i in range(row):
for j in range(col):
result[j][row-1-i] = array[i][j]
return result