프로그래머스 구현 대비 자물쇠와 열쇠

yjkim·2023년 6월 13일
0

알고리즘

목록 보기
16/60

문제: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을 풀어서 각각의 인자로 전달합니다.

라고 챗지피티가 그러네요

profile
We may throw the dice, but the Lord determines how they fall

0개의 댓글