자물쇠와 열쇠 (feat. 프로그래머스, 60059번)

자물쇠와 열쇠
https://programmers.co.kr/learn/courses/30/lessons/60059

프로그래머스

반응형

# woohyeon.kim
def spin_right(arr):
    return list(map(list, zip(*arr[::-1])))

def spin_left(arr):
    return list(map(list, zip(*arr))[::-1])

def check(arr, N):
    answer = True
    for ix in range(N):
        for iy in range(N):
            if arr[ix + N][iy + N] != 1:
                return False
    return answer

def solution(key, lock):
    M = len(key)
    N = len(lock)
    # 3배 더 큰 자물쇠 생성
    new_lock = [[1] * N * 3 for _ in range(N * 3)]
    # 기존 자물쇠를 새로운 자물쇠 가운데에 위치
    for ix in range(N):
        for iy in range(N):
            new_lock[ix + N][iy + N] = lock[ix][iy]
    # 시계방향으로 4번 돌림
    for _ in range(4):
        key = spin_right(key)
        for lock_ix in range(N * 2):
            for lock_iy in range(N * 2):
                # key를 new_lock에 꽂음
                for key_ix in range(M):
                    for key_iy in range(M):
                        new_lock[lock_ix + key_ix][lock_iy + key_iy] += key[key_ix][key_iy]
                # new_lock의 중앙만 확인
                if check(new_lock, N):
                    return True
                # key를 new_lock에서 뺌
                for key_ix in range(M):
                    for key_iy in range(M):
                        new_lock[lock_ix + key_ix][lock_iy + key_iy] -= key[key_ix][key_iy]
    return False
# *&)*@*

공부하던 도중 문제풀이로 있어 참고하며 해보았습니다.

내 머리로는 도저히 나오지 못했을 방법이네요...

key를 회전해야 한다는 것은 명확합니다.

문제가 되는건 key를 상하좌우로 이동시켜야 한다는 것인데요.

그래서 자물쇠를 3배 크게 만들었습니다. (N >= M 이라는 조건에 의해서요)

그리고 기존 자물쇠를 새로운 자물쇠의 가운데에 배치하고 key를 새로운 자물쇠의 처음부터 끝까지 매칭시켜줍니다.

만약 매칭되지 않으면 시계 방향으로 key를 회전 후 다시 합니다.

​

어떻게 이런 생각을 할 수 있는걸까요.