문제 링크

개요

  • 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 라이브러리를 활용해 비교적 단순한 방법으로 풀 수 있었다.

해설 코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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