[BOJ]9934 : 완전 이진 트리 C++ 문제 풀이

[BOJ]9934 : 완전 이진 트리 C++ 문제 풀이

728x90

백준 9934번

: 완전 이진 트리

재귀 호출을 사용해서 left와 right값을 업데이트 해 center값을 정하는 과정으로 생각.

//9934 완전 이진 트리 #include #include using namespace std; void findCenter(int * arr, int left, int right) { int center = (left + right) / 2; if (left == right) { cout << arr[center]; return; } cout << arr[center]; findCenter(arr, left, center - 1); findCenter(arr, center + 1, right); } int main() { int k; cin >> k; int size_k = pow(2, k) - 1; int* arr = new int[size_k]; for (int i = 0; i < size_k; i++) { cin >> arr[i]; } // 1 6 4 3 5 2 7 findCenter(arr, 0, size_k - 1); return 0; }

초안 코드, array의 왼쪽부터 우선 탐색해서 3 6 2 1 4 5 7 이렇게 답이 나와야 하는데 3 6 1 4 2 5 7 이렇게 노드에 대해서 왼쪽, 오른쪽을 먼저 출력하는 버그가 발생했다.

결국 왼쪽 이분 탐색을 호출하고, 바로 오른쪽 이분 탐색을 수행해야 하는 상황인 것이다.

//9934 완전 이진 트리 #include #include #include using namespace std; int k; vector order; vector answer[11]; void findCenter(int left, int right, int depth) { if (depth == k) return; if (left == right) { answer[depth].push_back(order[left]); return; } int center = (left + right) / 2; answer[depth].push_back(order[center]); findCenter( left, center - 1, depth + 1); findCenter(center + 1, right, depth + 1); } int main() { cin >> k; int size_k = pow(2, k) - 1; // 노드의 개수 for (int i = 0; i < size_k; i++) { int num; cin >> num; order.push_back(num); } // 1 6 4 3 5 2 7 findCenter(0, order.size(), 0); // 깊이에 따라 출력 for (int i = 0; i < k; i++) { // overflow 에러 for (int j = 0; j < answer[i].size(); j++) { cout << answer[i][j] << " "; } cout << endl; } return 0; }

방식을 바꾸어서, order배열과 answer배열로 나누어 문제를 풀었다. 문제의 핵심은 depth변수를 따로 둬서, answer 벡터에 이차원 벡터의 형식으로 넣는 것이다. 이전에 사용했던 방식은 노드 간의 깊이를 따로 확인할 수 없어서 출력에 어려움이 있었지만, answer벡터에 depth 별로 다르게 push_back을 진행해 재귀 호출 시에도 depth+1로 스택에 쌓이는 순서에 따라 나누어서 answer벡터에 담을 수 있었다.

728x90

from http://mingyum119.tistory.com/113 by ccl(A) rewrite - 2021-11-04 01:00:58