프로그래머스 레벨3 - 카카오 2020 자물쇠와 열쇠

문제주소

programmers.co.kr/learn/courses/30/lessons/60059

코딩테스트 연습 - 자물쇠와 열쇠

내 풀이

import copy
def solution(key, lock):
    answer = False
    n = len(lock)
    m = len(key)
    # 초기화
    layout = [[0] * (n+2*(m-1)) for _ in range(n+2*(m-1))] 
    for i in range(n):
        for j in range(n):
            layout[i+m-1][j+m-1] = lock[i][j]        
    # 대입
    for rotateNum in range(4):
        key = rotate(key)
        for i in range(m+n-1):
            for j in range(m+n-1):
                newLayout = copy.deepcopy(layout)
                result = checkTrue(putKey(key, newLayout, i, j), m, n)
                if result :
                    return True
    return answer

def rotate(puzzle):
    puzzleRotated = [[0]*len(puzzle) for _ in range(len(puzzle))]
    for i in range(len(puzzle)):
        for j in range(len(puzzle)):
            puzzleRotated[i][j] = puzzle[len(puzzle)-1-j][i]
    return puzzleRotated

def putKey(key, layout,i,j):
    for s in range(len(key)):
        for k in range(len(key)):
            layout[i+s][j+k] += key[s][k]
    return layout

def checkTrue(keyinlayout, m, n):
    for i in range(m-1, m+n-1):
        for j in range(m-1, m+n-1):
            if keyinlayout[i][j] != 1 :
                return False
    return True

ㅎㅎㅎ... 완전탐색으로 풀었다. for문을 몇개를 돌린건지😂😂 새롭게 알게된 것은 2차원 배열을 쓸 때는 deepcopy를 사용하는게 안전하다는 것, 복잡할 땐 함수를 분리하는게 최고다! 2중배열의 rotate 함수의 구현방법!

내가 사용한 접근 방식은 lock이 4*4 배열이고 key 가 3*3 배열이면 2+4+2 의 8*8 배열을 만들어 주는 것!

layout 배열

다른 사람 풀이

다들 풀이가 길어서 다른사람 풀이가 잘 이해가 안 간다. 😥 좀 더 for문을 줄이고 풀 수 있을 것 같은데.. 잘 모르겠다ㅎㅎㅎ  뭔가 numpy라는 라이브러리를 사용하면 행렬의 연산을 쉽게 하는 것 같았다. layout에 key를 넣어서 다시 셋팅해보는 부분을 고칠 수 있을 것 같은데.. 잘 모르겠다~ㅎㅎㅎ

정리

숫자가 작으면 완전탐색도 괜찮다! 복사는 안전하게  deepcopy해서 쓰자!