[프로그래머스 Programmers][Python] 자물쇠와 열쇠

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

코딩테스트 연습 - 자물쇠와 열쇠 | 프로그래머스

깡으로 구현해야한다.

 

우선 맵을 2*len(key) + len(lock) 으로 확장한 뒤에 arr[M][M] 에서부터 lock을 복사해 놓는다.

 

이제부터는 순서가 중요하다.

1. 아까의 arr 맵을 복사해 tmparr 에 넣는다.
2. key + lock 사이즈 동안 for문을 돌린다.
   1. key를 tmpkey에 복사해놓는다.
   2. tmpkey를 90도씩 4번 돌릴 수 있게 for문을 만든다.
      1. 각 tmparr에 더한다.
      2. arr 의 lock 위치가 다 1인지(0 이면 안되고, 2면 겹치는거니까 안된다) 확인해서 맞으면 true 반환
      3. tmparr 를 제자리에 놓는다
      4. (사실 여기서 tmpkey를 90도 돌린다)

 

엄청 느리다. 그래도 답은 나온다.

from copy import deepcopy

#https://stackoverflow.com/questions/8421337/rotating-a-two-dimensional-array-in-python
def rotated(array_2d):
    list_of_tuples = zip(*array_2d[::-1])
    return [list(elem) for elem in list_of_tuples]


def solution(key, lock):

    M = len(key)
    N = len(lock)

    arr = [[0 for _ in range(2*M + N)] for _ in range(2*M + N)]

    for i in range(N):
        for j in range(N):
            arr[M+i][M+j] = lock[i][j]

    tmparr = deepcopy(arr)
    for i in range(M+N+1):
        for j in range(M+N+1):
            tmpkey = deepcopy(key)
            for r in range(4):
                isOK = 0
                for y in range(M):
                    for x in range(M):
                        tmparr[i+y][j+x] += tmpkey[y][x]

                for y in range(N):
                    for x in range(N):
                        if tmparr[M+y][M+x] ==1:
                            isOK+=1

                if isOK == N*N:
                    return True


                tmpkey = rotated(tmpkey)
                tmparr = deepcopy(arr)


    return False