23.03.13 파이썬 코딩 퀴즈#194 자물쇠와 열쇠 (프로그래머스 스쿨)

이번 문제는 자물쇠와 열쇠 문제이다.

2020년 카카오 블라인드 채용 문제이고, 역시나 카카오 문제답게 설명이 길고 복잡하다.

열쇠를 나타내는 2차원 배열 key 와 자물쇠를 나타내는 2차월 배열 lock 이 매개변수로 주어질 때, 열쇠로 자물쇠를 열수 잇다면 True, 아니라면 False를 반환하면 된다.

한가지 중요한 점은 열쇠는 회전할 수 있으며, 자물쇠의 돌기(1)와 열쇠의 돌기(1)가 만나면 안된다.

예시 1를 그림으로 나타내면 위와 같은 형태이다. 이때 열쇠를 시계방향으로 90도 회전하게 되면 두 부분이 일치가 된다.

위 그림을 참조하면 이해하기 쉽다. 즉 옆이나 상하로 열쇠가 삐져나가도 문제가 없다.

행렬의 회전의 경우, argument unpacking 과 zip 을 활용하면 쉽게 해결 가능하다.

문제는 위 그림처럼 겹치는 부분을 만드는 것이다.

 

처음에는 자물쇠의 잠긴 부분과 열쇠의 돌출된 부분의 좌표를 활용하여 문제에 접근하였으나, 모든 좌표에 대하여 접근을 하는게 쉽지 않다는 걸 알 수 있었다.

구글링을 통해 검색해본 결과, 새로운 판 가운데 자물쇠를 두고 열쇠를 이동하며 맞춰보는 방법이 대다수였다.

반복문이 5중으로 쓰여졌다... 

먼저 위에서부터 차례대로 살펴보면, n 과 m 은 lock 과 key 의 길이이며, 이는 탐색을 할때 사용된다.

board는 n 을 기준으로 가로/세로가 3배 더 긴 0으로 채워진 2차원 배열이며, 이 때 board의 중앙에 lock 값들을 넣어준다.

3배를 하였기 때문에 단순하게 i+n, j+n 으로 중앙에 위치시킬 수 있다.

그리고 이제 본격적으로 board를 탐색하게 되는데, 보드를 탐색할 값의 기준을 n*2 까지 이다.

쉽게 생각해서 lock 이 3x3 이였다면, board 는 9x9 가 된다. 그리고 key 는 lock 보다 크기가 작거나 같기 때문에 (1,1)에서 부터 탐색을 시작해서 (1,8) 까지 탐색을 하지만, 사실은 n*2 를 벗어나면 겹치는 부분이 없기 때문에 n*2 까지만 탐색하게 된다. 3번째 반복문에 의해 매 번 키값은 회전하게 된다.

이제 m (len(key))를 기준으로 해당 board 에 key 값을 전달해준 다음, check() 함수를 통해 해당 board 의 참, 거짓을 확인하게 된다.

마찬가지로 전달받은 배열(board)의 길이를 3등분 한 다음에, 그 가운데 부분인 n, n*2 까지만 값을 확인해 주면 된다.

만약 1이 아닌 0 또는 2 가 존재한다면, 이는 자물쇠가 열리지 않았거나 키의 돌출부분과 자물소의 돌출 부분이 만난다는 의미이므로 바로 False 를 반환하면 된다.

 

그리고 만약 False 인 경우라면, 다시 board 값을 원상태로 돌려준 후, key 배열을 회전시켜 주면 된다.

(해당 key 의 회전 원리는 구글링을 통해 공부해보자)