TL;DR
최근 모사에서 하는 코딩 테스트를 진행했다. 상당히 독특한 문제를 만났다. 당시에는 풀지 못하고 넘어갔는데 적당한 접근 방법을 찾았다.
문제
아래 그림과 같은 구조의 자료가 있다.
- 숫자 쓰기는 맨 위 칸을 1로 하고 한 칸씩 시계방향으로 돌아가며 1씩 증가시킨다.
- 읽기는 맨 위 칸을 시작으로 한 층씩 내려가며 왼쪽에서 오른쪽 방향으로 읽는다.
후기
우선 문제를 해결하지 못했다. 패턴에서 수식을 찾아보려고 했는데 쉽지 않았다. 수식을 못 찾으면 적합한 자료구조를 선택하고 거기에 값을 쓰고 읽는 방식으로 해야한다. 자료구조는 트리로 해야 할 것 같았는데 거기까지만 접근하고 다른 문제 푸느라 시간을 다 써버리는 바람에 손도 못 댔다.
그러다 잠자리에 들어서는 갑자기 아이디어가 떠올랐다. 그걸 기록하는게 이번 포스트의 목적이다.
풀이
- 우선 데이터를 어떻게 표현할지 결정을 해야 한다. 처음엔 트리를 고려했다. 형태 자체는 Binary Tree 로 볼 수 있을 것 같았다. 읽기 과정을 BFS(너비 우선 탐색, Breadth First search)를 기반으로 약간 수정을 해서 쓸 수 있을 것 같았다. 하지만 트리를 쓸 경우 독특한 쓰기 과정을 구현하는게 쉽지 않을 것 같았다.
- 자기 전에 떠 오른 아이디어는 이 육각형 구조를 살짝 돌리면 배열처럼 접근할 수 있지 않을까 하는 것이었다. 뭔가 영화 인셉션이나 닥터 스트레인지 처럼 공간을 왜곡시키는 방법이 떠올랐다.
대략 이런 모습이다. 트리보다 배열이 훨씬 다루기 쉬우므로 이게 하나의 방법일 수 있을 것 같다.
배열을 이용한 접근법
배열을 쓴다고 했을 때 적합한 표기 방법은 아래와 같다. 엑셀로 여러 방법을 시도해 봤는데 그나마 패턴이 보이는게 이 방법이었다. 오른쪽에 셀별 배경 색으로 읽기 순서를 구분했다. 쓰기도, 읽기도 쉽게 패턴을 추측할 수 있다. 배열 인덱스의 움직이는게 좀 괴랄할 것 같긴 하지만 충분히 해결 가능한 방법이다.
감상
- 왜 잠들기 전에 이런 아이디어가 나오는 걸까.. 테스트 보고 나서 크게 신경 쓰지 않았었는데..
- 효율적인 접근 방법을 찾지 못하면 풀기 어려운 문제인 것 같다. 비슷한 문제를 접해본 적이 없는 사람은 손대기 어렵지 않았을까..
- 잘 하는 사람들은 쉽게 풀었겠지…몇 줄 수식으로 풀어버릴 수 있는거 아닐까..ㅠ