문제:https://school.programmers.co.kr/learn/courses/30/lessons/60059
엄청 빡센 빡구현문제
import copy
def rotate(key):
newkey=[[0 for i in range(len(key))] for j in range(len(key))]
for i in range(len(key)):
for j in range(len(key)):
newkey[i][j]=key[j][len(key)-i-1]
return newkey
def solution(key, lock):
m=len(key)
n=len(lock)
answer=True
alock=[[0 for i in range(n+2*m)] for j in range(n+2*m)]
for i in range(n):
for j in range(n):
alock[i+m][j+m]=lock[i][j]
for i in range(4):
for j in range(n+m):
for w in range(n+m):
check=True
newlock=copy.deepcopy(alock)
#시작지점=[j,w]
for a in range(m):
for b in range(m):
newlock[a+j][b+w]+=key[a][b]
for a1 in range(n):
for b1 in range(n):
if newlock[a1+m][b1+m]==1:
continue
else:
check=False
if check:
return True
# 모든 코드가 끝나고 한번 회전
key=rotate(key)
return False
키를 4가지 방향으로 회전시켜 주는 rotate 함수 구현해주고
자물쇠를 (2xn+m)*(2xn+m) 만큼 확장 시켜주고 가운데에 자물쇠를 넣음
0,0 좌표부터 n+m,n+m좌표까지 키를 자물쇠에 넣어보고 알맞으면 true 아니면 continue
시간복잡도 대충 계산하면
10^9x2
최대 10억? 개많네
배열 회전할때 list(zip(*reversed(List))) 써주면 편하다
zip(reversed(key))는 reversed(key)에서 얻은 행들을 열 단위로 묶어주는 함수입니다. zip() 함수는 여러 개의 iterable을 인자로 받아, 각 iterable에서 동일한 인덱스의 요소들을 묶어서 튜플로 반환합니다. 연산자를 사용하면 iterable을 풀어서 각각의 인자로 전달합니다.
라고 챗지피티가 그러네요