[프로그래머스/python] 자물쇠와 열쇠

⏰ 소요 시간 : 1시간

나의 풀이

0. n,m의 크기가 작아(20) 브루트 포스가 적합할 것이라고 판단했습니다
1. 키가 자물쇠를 벗어나는 경우를 처리하기 위해 배열 크기를 확장(n+(m-1)*2)
2. 모든 배열의 좌표를 순회하며 키와 자물쇠의 숫자를 합함.
3. 이때 key를 90, 180, 270, 360도 회전하며 모든 경우를 대조.
4. 배열 내 자물쇠 영역의 모든 숫자가 1이라면 키와 열쇠가 일치한다고 판단.

import copy

def solution(key, lock):
    answer = False
    n = len(lock)
    m = len(key)
    v_lock = [[0] * (n+(m-1)*2) for _ in range(n+(m-1)*2)]
    for i in range(n):
        for j in range(n):
            v_lock[i+(m-1)][j+(m-1)] = lock[i][j]
    test_lock = copy.deepcopy(v_lock)
    for i in range(n+m-1):
        for j in range(n+m-1):
            for _ in range(4):
                key = rotate90(key)
                for k in range(m):
                    for l in range(m):
                        test_lock[i+k][j+l] += key[k][l]
                if isFit(test_lock, n, m): return True
                else: test_lock = copy.deepcopy(v_lock)
    return answer

def rotate90(key):
    m = len(key)
    ret = [[0] * m for _ in range(m)]
    for r in range(m):
        for c in range(m):
            ret[c][m-1-r] = key[r][c]
    return ret

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