자물쇠와 열쇠 풀이

자물쇠와 열쇠 풀이

코드

import numpy as np
def solution(key, lock):
    N, M = len(lock), len(key)
    lock = np.pad(lock, ((M-1,M-1),(M-1,M-1)), 'constant', constant_values=0)
    for _ in range(4) :
        key = rotate(key)
        for i in range(M+N-1) :
            for j in range(M+N-1) :
                lock_ = np.array(lock)
                lock_[i:i+M, j:j+M] ^= key
                if lock_[M-1 : N + M-1, M-1 : N + M-1].sum() == N**2 :
                    return True
    return False

def rotate(key):
    return np.array(list(zip(*key[::-1])))

문제에 관하여

사실 이문제는 푸는것은 어렵지 않았습니다. 제가 코드를 깔끔하고 센스있게 짜야하는 강박증이있어서 어떻게해야 한줄이라도 줄일까 하는 고민을 참 많이했던 문제입니다. 그 고민 중핵심은 rotate입니다. 구글링을 통해 2차원 배열을 zip()을 통해 한줄로 해결한 글을 보고 충격을 받았었습니다. 이해하는데 쪼금 애를 먹었지만 값진 공부였습니다.

알고리즘

N x N의 자물쇠가 M x M의 열쇠로 풀리는가? 에대한 문제입니다. 알고리즘은 이렇습니다.

N x N 자물쇠를 (N+M-1) x (N+M-1)크기로 padding

열쇠로 자물쇠 전체를 훑으며 xor연산을 하고 가운데에있는 원본 자물쇠 N x N의 합이 N**2이 되면 True

열쇠를 회전한 후 다시 훑으며 xor 반복

간단합니다. 배열 문제치고 알맹이가 없는 겉보기만 극악의 문제입니다. 핵심은

padding 후의 자물쇠의 정확한 index 인지

rotate 함수 만들기

이렇습니다.

rotate

def rotate(key):
    return np.array(list(zip(*key[::-1])))

제가 참고한 zip을 이용한 2차원 배열 회전 블로그 입니다.

우선 이 코드를 제일 안에서부터 하나하나 까보겠습니다.

[ : : -1]

[::-1]방식

[::-1]인덱싱은 Iterable객체 안의 원소들을 거꾸로 출력해줍니다.

zip(*key[ : : -1])

c언어도아닌데 붙어있는 *… 이것의 쓰임새를 알려면 우선 zip()을 알아야합니다.

zip은 두개 이상의 서로다른 iterable 객체들의 원소를 하나씩 묶어주는 함수입니다. 쉽게말하면 각반의 1등끼리 한조만들고 2등끼리 한조 만들고 이런 역할을 해주는 함수입니다.

실제 코드로 보면

a = [1,2,3,4,5]
b = ['a', 'b', 'c']
c = ['one', 'two', 'three', 'four']

for i in zip(a, b, c) :
  print(i)

output : (1, 'a', 'one') (2, 'b', 'two') (3, 'c', 'three')

각 iterable객체의 길이가 달라도 최소 길이의 객체에 맞춰 출력합니다.

그렇다면 *이놈은 도대체 무엇을 하는 놈일까… 바로 zip()이하는 일을 비슷하게 해주는 놈입니다.

zip(*)

zip()은 서로다른 두 iterable 객체의 원소들을 하나씩 묶어서 iterable객체를 return

zip(*)은 한 iterable 객체안의 리스트의 각 index끼리 묶어서 재정리한 객체를 return

*가 붙으면 내부 iterable 객체를 처리합니다. 실제 코드로 보시죠

a = [1, 2, 3]
b = ['one', 'two', 'three']
c = list(zip(a, b)) # c = [(1, 'one'), (2, 'two'), (3, 'three')]
d = list(zip(*c)) # d = [(1, 2, 3), ('one', 'two', 'three')]

이런식으로 됩니다. 그렇다면 이게 진짜 배열을 회전시키는지 한번 봅시다.

padding & indexing

N x N 자물쇠에 꼭 열쇠가 안들어맞아도 됩니다.

이런식으로 자물쇠 바깥으로 열쇠가 나가도 아구가 맞으면 자물쇠가 풀립니다. 그렇다면 자물쇠에 padding을 해준다면 얼마를 해주어야 할까요? padding된 자물쇠 (0, 0)과 열쇠의 (0, 0)이 맞물려도 최소한 열쇠의 한칸이 자물쇠 한칸에 들어가게 하려면 열쇠의 길이 - 1만큼 padding을 해주어야 합니다. 전체 그림으로 한번 보시죠

padding size : M-1

padding된 자물쇠에서 원본 자물쇠 인덱스 : [M-1 : N+M-1]

탐색 인덱스 : [:M+N-1]

import numpy as np
def solution(key, lock):
    N, M = len(lock), len(key)
    lock = np.pad(lock, ((M-1,M-1),(M-1,M-1)), 'constant', constant_values=0) # 0으로 M-1씩 패딩
    for _ in range(4) :
        key = rotate(key) # key 회전
        for i in range(M+N-1) :
            for j in range(M+N-1) :
                lock_ = np.array(lock) # lock 복사본 lock_
                lock_[i:i+M, j:j+M] ^= key # 현재 key와 lock이 물려있는 구간에서의 xor 연산
                if lock_[M-1 : N + M-1, M-1 : N + M-1].sum() == N**2 :
                    return True
    return False

def rotate(key):
    return np.array(list(zip(*key[::-1])))

이정도면 코드를 이해하는데 충분할겁니다.

자물쇠와 열쇠