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

문제 링크

---

풀이

Key(M $\times$ M)를 상하좌우 움직이며 회전시켜서 Lock(N $\times$ N)의 요철과 딱 맞아 떨어진다면 True, 아니면 False를 반환하는 문제이다.

Key 배열의 이동을 위해서 배열을 직접 이동시키는 방법을 고민하다가,
아래와 같은 방법으로 배열의 이동을 구현했다.

N=4, M=4 일 때, 아래와 같은 배열을 만들어준다.
비어있는 부분은 모두 0으로 채워져있다.

아래와 같이 만들어진 키 테이블을 순회하면,
주어진 키의 이동을 구현할 수 있다.

그리고 매 이동마다 한 바퀴 회전하며 lock 배열과 완전히 일치하지 않는지 확인한다.
만약, 같은 좌표에 하나라도 같은 값이 존재한다면 False,
그렇지 않다면 True이다.

---

코드

def solution(key, lock):
    key_size = len(key)
    lock_size = len(lock)
    KEY_TABLE_SIZE = 3*lock_size-2
    KEY_TABLE = [[0] * KEY_TABLE_SIZE for _ in range(KEY_TABLE_SIZE)]
    lock_sum = 0

    for i in range(key_size):
        lock_sum += sum(lock[i])
        for j in range(key_size):
            KEY_TABLE[i+lock_size-1][j+lock_size-1] = key[i][j]
    if lock_sum == key_size**2:
        return True
    for i in range(KEY_TABLE_SIZE-lock_size+1):
        for j in range(KEY_TABLE_SIZE-lock_size+1):
            temp_key = make_key(KEY_TABLE, i, j, lock_size)
            for _ in range(4):
                temp_key = rotate(temp_key)
                if compare(lock, temp_key):
                    return True
    return False


def compare(lock, key):
    for i in range(len(key)):
        for j in range(len(key)):
            if lock[i][j] == key[i][j]:
                return False
    return True


def make_key(key, x, y, N):
    result = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            result[i][j] = key[i+x][j+y]
    return result


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