[프로그래머스] 자물쇠와 열쇠 / Python / 2020 KAKAO BLIND RECRUITMENT

https://programmers.co.kr/learn/courses/30/lessons/60059?language=python3

프로그래머스

---

---

Solution

	import copy
	def unlock(m, n, key, lock, tmp_lock):
	k = 0
	while True:
	if k == (n+m-1)**2:
	break
	copy_tmp_lock = copy.deepcopy(tmp_lock)
	x = k % (n+m-1)
	y = k // (n+m-1)
	for i in range(y, y+m):
	for j in range(x, x+m):
	if copy_tmp_lock[i][j] == 1 and key[i-y][j-x] == 1:
	break
	if copy_tmp_lock[i][j] == 0 and key[i-y][j-x] == 1:
	copy_tmp_lock[i][j] = 1
	result = 0
	for i in range(m-1, n+m-1):
	for j in range(m-1, n+m-1):
	result += copy_tmp_lock[i][j]
	if result == n**2:
	return True
	else:
	k+=1
	return False
	def rotation_key(m, key):
	rotationed = []
	for i in range(m):
	tmp = []
	for j in range(m-1, -1, -1):
	tmp.append(key[j][i])
	rotationed.append(tmp)
	return rotationed
	def solution(key, lock):
	n = len(lock)
	m = len(key)
	tmp_lock = [[0] * (2*m+n-2) for _ in range(2*m+n-2)]
	for i in range(m-1, n+m-1):
	for j in range(m-1, n+m-1):
	tmp_lock[i][j] = lock[i-(m-1)][j-(m-1)]
	cnt = 0
	while cnt < 5:
	flag = unlock(m, n, key, lock, tmp_lock)
	if flag:
	return True
	key = rotation_key(m, key)
	cnt += 1
	return False

view raw 자물쇠와열쇠.py hosted with ❤ by GitHub

 

구현해야할 것

• 열쇠 회전
• 열쇠가 자물쇠에 걸쳐있을 때의 최대 크기로 또 다른 배열 생성
• 열쇠 이동

 

주의할 점

• 자물쇠 영역 바깥에서의 열쇠 상태는 영향이 없다.
• 자물쇠 영역 내에서는 열쇠의 돌기와 자물쇠의 홈 부분이 정확히 일치하여야 한다.
• 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안된다.
• 자물쇠가 비어있는 곳이 없어야 한다.

자물쇠와 열쇠의 크기가 작으므로 모든 경우를 탐색한다. 그리고 이 문제의 경우 열쇠가 자물쇠에 걸칠 수 있기 때문에 배열을 하나 더 만들어 주어야 한다. 

 

 

위와 같이 왼쪽 위 부터 모든 경우에 걸칠 수 있는 최대 크기로 배열을 만들어준다. 이때 배열의 크기는 n+2(m-1) X n+2(m-1) 이다. 그리고 생성한 배열 중앙에 자물쇠의 상태를 넣어준다. 그리고 열쇠를 한 칸씩 이동할 때마다 배열 중앙에 있는 자물쇠의 합이 n X n이 되는지 검사한다. 나는 테스트케이스에 너무 집착한 나머지 자물쇠의 합이 9로 되는지만 검사하고 계속 틀렸었다. 진짜 다 풀어 놓은걸 이 놈 하나 때문에 시간을 얼마나 버렸는지😡