프로그래머스 종이접기 / 이진 트리, 순회 / JAVA

이번에 살펴볼 문제는 프로그래머스의 <종이접기> 문제이다.

https://programmers.co.kr/learn/courses/30/lessons/62049

코딩테스트 연습 - 종이접기

종이를 계속 반으로 접어서 안으로 파인 부분(∨)은 0, 밖으로 볼록 튀어나온 부분(∧)은 1로 순서대로 출력하면 되는 문제이다. 이 문제는 규칙성을 찾고 적절한 자료구조를 찾아서 탐색하면 그렇게 어렵지 않게 풀 수 있는 문제이다. 다만, 개인적으로 처음에 생각하기가 조금 쉽지 않았던 것 같다.

한 번 접었을 때는 오목 하나 있으므로 [0] 이고, 두 번 접었을 때는 앞에 접힌 부분 사이사이로 0,1을 추가해서 [0,0,1]과 같이 나타난다. 세 번 접었을 때는 그 이전 접힌 부분에서 0,1,0,1을 추가해서 [0,0,1,0,0,1,1] 과 같이 반환해 주면 된다. 규칙성은 금방 찾았는데 이를 어떻게 나타내 줄 지가 생각이 바로 나지 않았던 것 같다.

결국 찾은 방법은 이진 트리를 사용하자는 것이었다. 트리의 뎁스가 하나씩 늘어날 때마다, 한 번씩 종이가 접힌다는 의미이며, 부모노드에서 자식 노드로 0,1을 뻗어서 계속 나아가 주면 된다. 그리고 나서 다음과 같은 순서로 순회해서 결과값을 반환하면 된다.

이 방법은 세 가지의 순회 방법 중 중위 순회(in-order traversal)에 속한다. 왼쪽 -> 가운데 -> 오른쪽 순으로 탐색을 하는 순서이다. 적절하게 이진 트리를 만들어 주고 중위 순회로 결과를 출력해 주면 문제를 풀 수 있다.

오랜만에 트리의 순회를 다시 상기시켜 준 고마운 문제이다. 문제에 적절하게 잘 적용하는 연습도 하면 좋을 것 같다!