이번에 살펴볼 문제는 프로그래머스의 <종이접기> 문제이다.
https://programmers.co.kr/learn/courses/30/lessons/62049
코딩테스트 연습 - 종이접기
직사각형 종이를 n번 접으려고 합니다. 이때, 항상 오른쪽 절반을 왼쪽으로 접어 나갑니다. 다음은 n = 2인 경우의 예시입니다. 먼저 오른쪽 절반을 왼쪽으로 접습니다. 다시 오른쪽 절반을 왼쪽��
programmers.co.kr
종이를 계속 반으로 접어서 안으로 파인 부분(∨)은 0, 밖으로 볼록 튀어나온 부분(∧)은 1로 순서대로 출력하면 되는 문제이다. 이 문제는 규칙성을 찾고 적절한 자료구조를 찾아서 탐색하면 그렇게 어렵지 않게 풀 수 있는 문제이다. 다만, 개인적으로 처음에 생각하기가 조금 쉽지 않았던 것 같다.
한 번 접었을 때는 오목 하나 있으므로 [0] 이고, 두 번 접었을 때는 앞에 접힌 부분 사이사이로 0,1을 추가해서 [0,0,1]과 같이 나타난다. 세 번 접었을 때는 그 이전 접힌 부분에서 0,1,0,1을 추가해서 [0,0,1,0,0,1,1] 과 같이 반환해 주면 된다. 규칙성은 금방 찾았는데 이를 어떻게 나타내 줄 지가 생각이 바로 나지 않았던 것 같다.
결국 찾은 방법은 이진 트리를 사용하자는 것이었다. 트리의 뎁스가 하나씩 늘어날 때마다, 한 번씩 종이가 접힌다는 의미이며, 부모노드에서 자식 노드로 0,1을 뻗어서 계속 나아가 주면 된다. 그리고 나서 다음과 같은 순서로 순회해서 결과값을 반환하면 된다.
이 방법은 세 가지의 순회 방법 중 중위 순회(in-order traversal)에 속한다. 왼쪽 -> 가운데 -> 오른쪽 순으로 탐색을 하는 순서이다. 적절하게 이진 트리를 만들어 주고 중위 순회로 결과를 출력해 주면 문제를 풀 수 있다.
오랜만에 트리의 순회를 다시 상기시켜 준 고마운 문제이다. 문제에 적절하게 잘 적용하는 연습도 하면 좋을 것 같다!
'Computer Sci. > Algorithms' 카테고리의 다른 글
| 백준 1507 / 플로이드 와셜(Floyd Warshall) 알고리즘 / JAVA (0) | 2020年06月24日 |
|---|---|
| 백준 2352 / LIS(최장 증가 수열), DP / JAVA (0) | 2020年06月17日 |
| 백준 3176 / LCA 알고리즘, DP, DFS / JAVA (2) | 2020年05月20日 |
| 카카오 19겨울인턴 4번 / 유니온 파인드(Union Find) / JAVA (0) | 2020年05月11日 |
| 백준 9202 / 트라이(Trie), DFS / JAVA (0) | 2020年05月08日 |