[프로그래머스/카카오 60059] 자물쇠와 열쇠 (Python)

2022. 5. 6. 17:53

문제 링크 #

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

개요 #

numpy 라이브러리와 중복 순열을 사용해 해결할 수 있는 문제다.

문제 조건 #

2차원 배열인 열쇠(M)를 회전하거나 이동해 2차원 배열인 자물쇠(N)에 맞는지 여부를 반환하는 문제다.

문제 해설 #

2차원 배열을 numpy.ndarray 형식으로 변환하면 회전 및 이동 연산을 쉽게 처리할 수 있다.
90도 단위로 4번 회전된 각각의 목록을 구하고 상하좌우 이동을 위해 바깥쪽에 0으로 채워진 padding을 추가한다.
padding이 채워진 N+M-1크기의 2차원 배열에 대해 자물쇠 크기만큼의 부분만 잘라내어 자물쇠의 구멍과 비교한다.
OR 연산 시 자물쇠가 1로 채워지고 열쇠와 자물쇠 사이에 겹치는 부분이 없다면 열쇠가 자물쇠에 맞다고 판단한다.

시행착오 #

열쇠의 크기가 자물쇠의 크기보다 작을 경우를 고려하지 못하고 둘의 사이즈를 맞추는 과정을 무시해 에러가 생겼다.
처음엔 0으로 채워진 단일 행 또는 열과 concatenate 연산을 진행해 열쇠를 아래쪽과 오른쪽으로만 이동했는데,
그 반대의 경우를 고려하지 못해서 에러가 생겼다. 이후 padding을 사용하는 코드로 변경했다.
통계학적 지식이 부족해 인덱스 목록에 대해 중복 조합 연산을 했었는데 잘못됨을 인지하고 중복 순열로 변경했다.
열쇠와 자물쇠의 돌기가 만나선 안된다는 부분을 처리하지 않아 특정 케이스에 대해 실패가 발생하는 이유를 인지하지 못했다.
XOR 연산도 하나의 방법일 수 있지만 대신에 두 배열의 합을 사용해 중복되는 부분을 판단했다.
프로그래머스가 백준처럼 NumPy 라이브러리를 지원하지 않았다면 매우 난해한 문제였을테지만,
다행히 NumPy 라이브러리를 활용해 비교적 단순한 방법으로 풀 수 있었다.

해설 코드 #

python

import numpy as np
from itertools import product

def solution(key, lock):
    key, lock = np.array(key), np.array(lock)
    rotated_keys = [np.pad(np.rot90(key, i),len(lock)-1) for i in range(4)]

    index_list = list(range(len(rotated_keys[0])-len(lock)+1))
    for rotated_key in rotated_keys:
        for i, j in list(product(index_list, index_list)):
            key = rotated_key[i:i+len(lock),j:j+len(lock)]
            if (0 not in np.logical_or(key,lock)) and (2 not in (key + lock)):
                return True

    return False