자물쇠와 열쇠

https://school.programmers.co.kr/learn/courses/30/lessons/60059

프로그래머스

문제요약:

1과0으로 이루어진 2차원 자물쇠와 열쇠가 있을 때, 키로 열 수 있으면 True 아니면 Fasle를 반환.(회전가능)

난이도3

 

소요시간: 

45분

 

1차시도:

def turn_90(arr):
	return [i[::-1] for i in zip(*arr)]
	
def zero_padding(n,m,lock):		
	temp = [[0]*(n+2*(m-1)) for _ in range(n+2*(m-1))]							  
	for i in range(m-1,m-1+n):
		temp[i] = [0]*(m-1) + lock[i-(m-1)] + [0]*(m-1)
	return temp
	
def solution(key,lock):
	#m 은 key 크기 n 은 lock크기
	m = len(key)
	n = len(lock)
	
	for _ in range(4):
		key = turn_90(key)
		for i in range(n+m-1):
			for j in range(n+m-1):
				#i,j 는 lock내부에서 key의 시작점
				piv = 0
				temp = zero_padding(n,m,lock)
				for y in range(m):
					for x in range(m):
						#y,x는 옮겨다니는 key내부
						temp[y+i][x+j] += key[y][x] 
				#다 더한뒤
				piv = 0
					
				for ny in range(m-1,m-1+n):
					for nx in range(m-1,m-1+n):
						if temp[ny][nx] != 1:
							piv =1
							break
					if piv:
						break
				else:
					return True
						
	else:	
		return False

print(solution([[0, 0, 0], [1, 0, 0], [0, 1, 1]],[[1, 1, 1], [1, 1, 0], [1, 0, 1]]))

먼저 90도 회전을 오랜만에 생각해서 시간을 좀 소요했고(암기하자) , 제로패딩을 할때 0을 넣을 생각하지 말고 큰 0판에 가운데에 lock을 넣는게 훨씬 빠르게 풀었을 것 같다. ( 2(n-m+1) ) 해결하는데 10분 사용한듯함 주의하자)

나머진 시작지점 계속 바꿔주면서 임시에 더한 후, 원래 lock부분만 때와서 전부 1이면 True를 반환했다.