코딩 테스트

TL;DR

최근 모사에서 하는 코딩 테스트를 진행했다. 상당히 독특한 문제를 만났다. 당시에는 풀지 못하고 넘어갔는데 적당한 접근 방법을 찾았다.

문제

아래 그림과 같은 구조의 자료가 있다.

  • 숫자 쓰기는 맨 위 칸을 1로 하고 한 칸씩 시계방향으로 돌아가며 1씩 증가시킨다.
  • 읽기는 맨 위 칸을 시작으로 한 층씩 내려가며 왼쪽에서 오른쪽 방향으로 읽는다.

후기

우선 문제를 해결하지 못했다. 패턴에서 수식을 찾아보려고 했는데 쉽지 않았다. 수식을 못 찾으면 적합한 자료구조를 선택하고 거기에 값을 쓰고 읽는 방식으로 해야한다. 자료구조는 트리로 해야 할 것 같았는데 거기까지만 접근하고 다른 문제 푸느라 시간을 다 써버리는 바람에 손도 못 댔다.
그러다 잠자리에 들어서는 갑자기 아이디어가 떠올랐다. 그걸 기록하는게 이번 포스트의 목적이다.

풀이

  • 우선 데이터를 어떻게 표현할지 결정을 해야 한다. 처음엔 트리를 고려했다. 형태 자체는 Binary Tree 로 볼 수 있을 것 같았다. 읽기 과정을 BFS(너비 우선 탐색, Breadth First search)를 기반으로 약간 수정을 해서 쓸 수 있을 것 같았다. 하지만 트리를 쓸 경우 독특한 쓰기 과정을 구현하는게 쉽지 않을 것 같았다.
  • 자기 전에 떠 오른 아이디어는 이 육각형 구조를 살짝 돌리면 배열처럼 접근할 수 있지 않을까 하는 것이었다. 뭔가 영화 인셉션이나 닥터 스트레인지 처럼 공간을 왜곡시키는 방법이 떠올랐다.

대략 이런 모습이다. 트리보다 배열이 훨씬 다루기 쉬우므로 이게 하나의 방법일 수 있을 것 같다.

배열을 이용한 접근법

배열을 쓴다고 했을 때 적합한 표기 방법은 아래와 같다. 엑셀로 여러 방법을 시도해 봤는데 그나마 패턴이 보이는게 이 방법이었다. 오른쪽에 셀별 배경 색으로 읽기 순서를 구분했다. 쓰기도, 읽기도 쉽게 패턴을 추측할 수 있다. 배열 인덱스의 움직이는게 좀 괴랄할 것 같긴 하지만 충분히 해결 가능한 방법이다.

감상

  • 왜 잠들기 전에 이런 아이디어가 나오는 걸까.. 테스트 보고 나서 크게 신경 쓰지 않았었는데..
  • 효율적인 접근 방법을 찾지 못하면 풀기 어려운 문제인 것 같다. 비슷한 문제를 접해본 적이 없는 사람은 손대기 어렵지 않았을까..
  • 잘 하는 사람들은 쉽게 풀었겠지…몇 줄 수식으로 풀어버릴 수 있는거 아닐까..ㅠ

답글 남기기

이메일 주소는 공개되지 않습니다. 필수 항목은 *(으)로 표시합니다