✍ 문제
n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다.
이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.
✍ 입력
첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다.
다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 포스트오더가 주어진다.
✍ 출력
첫째 줄에 프리오더를 출력한다.
✅ 코드
❗ 메모리 초과 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void preTraversal(vector<int> inorder, vector<int> postorder, vector<int>& result) {
int index = postorder.size() - 1;
result.push_back(postorder[index]);
if (inorder.size() == 1 && postorder.size() == 1) return; // left, right subtree 모두 없는 경우
int root_index = find(inorder.begin(), inorder.end(), postorder[index]) - inorder.begin();
if (root_index != 0) { //left subtree가 있는경우
vector<int> left_in(inorder.begin(), inorder.begin() + root_index);
vector<int> left_post(postorder.begin(), postorder.begin() + root_index);
preTraversal(left_in, left_post, result);
}
if (root_index != inorder.size() - 1) { //right subtree가 있는경우
vector<int> right_in(inorder.begin() + root_index + 1, inorder.end());
vector<int> right_post(postorder.begin() + root_index, postorder.end()-1);
preTraversal(right_in, right_post, result);
}
}
int main() {
int num, temp;
vector<int> inorder;
vector<int> postorder;
vector<int> preorder;
cin >> num;
for (int i = 0; i < num; i++) {
cin >> temp;
inorder.push_back(temp);
}
for (int i = 0; i < num; i++) {
cin >> temp;
postorder.push_back(temp);
}
preTraversal(inorder, postorder, preorder);
for (int i = 0; i < preorder.size(); i++) cout << preorder[i] <<' ';
return 0;
}❗ 시간 초과 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void preTraversal(vector<int> inorder, vector<int> postorder, int in_l, int in_r, int post_l, int post_r) {
int index = post_r;
cout << postorder[index] << ' ';
if (in_l == in_r && post_l == post_r) return; // left, right subtree가 모두 없는 경우
int root_index = find(inorder.begin()+in_l, inorder.begin()+in_r+1, postorder[index]) - inorder.begin();
if (root_index > in_l) { //left subtree가 있는경우
preTraversal(inorder, postorder, in_l, root_index-1, post_l, post_l+root_index-in_l-1);
}
if (root_index < in_r) { //right subtree가 있는경우
preTraversal(inorder, postorder, root_index+1, in_r, post_r-in_r+root_index, post_r-1);
}
}
int main() {
int num, temp;
vector<int> inorder;
vector<int> postorder;
cin >> num;
for (int i = 0; i < num; i++) {
cin >> temp;
inorder.push_back(temp);
}
for (int i = 0; i < num; i++) {
cin >> temp;
postorder.push_back(temp);
}
preTraversal(inorder, postorder, 0, num-1, 0, num-1);
return 0;
}❗ 정답 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> inorder;
vector<int> postorder;
void preTraversal(int in_l, int in_r, int post_l, int post_r) {
int index = post_r;
cout << postorder[index] << ' ';
if (in_l == in_r && post_l == post_r) return; // left, right subtree가 모두 없는 경우
int root_index = find(inorder.begin()+in_l, inorder.begin()+in_r+1, postorder[index]) - inorder.begin();
if (root_index > in_l) { //left subtree가 있는경우
preTraversal(in_l, root_index-1, post_l, post_l+root_index-in_l-1);
}
if (root_index < in_r) { //right subtree가 있는경우
preTraversal(root_index+1, in_r, post_r-in_r+root_index, post_r-1);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int num, temp;
cin >> num;
for (int i = 0; i < num; i++) {
cin >> temp;
inorder.push_back(temp);
}
for (int i = 0; i < num; i++) {
cin >> temp;
postorder.push_back(temp);
}
preTraversal(0, num-1, 0, num-1);
return 0;
}✅ 코드 설명
❗ 알고리즘
이진트리의 중위와 후위 순회 결과값을 input으로 받았을 때 전위 순회 결과값을 출력해야하는 문제이다. 전위, 중위, 후위 순회 각각의 특징과 재귀를 이용하여 구현했고, 각 순회 결과값들은 vector를 이용하여 저장하였다.
- 중위 inorder: 특정 원소(root)를 기준으로 왼쪽에 위치한 원소들은 left subtree,
오른쪽에 위치한 원소들은 right subtree에 속한다. - 후위 postorder: 트리의 root값은 후위 순회의 가장 마지막 원소이다.
- 전위 preorder: 각 subtree에 대해 root값을 가장 먼저 방문한다.
이러한 특징을 고려해보았을 때, 내가 생각해낸 해결방법은 다음과 같다.
- 주어진 tree에 대한 root값을 후위 vector를 이용하여 찾는다. (맨 마지막 원소)
- 찾은 root값을 다시 전위 vector에서 찾는다.
- 전위 vector에서 찾은 root 값의 위치를 기준으로 왼쪽, 오른쪽으로 나누어 각각의 subtree에 대해 다시 1-3과정을 반복한다. (재귀 호출)
- 재귀적으로 함수를 호출하다가 tree의 원소가 1개가 되는 경우는 1번 과정만 진행하고 return 한다.
알고리즘 설계는 잘 되었으나, 이를 구현하는 과정에서 여러 오류들을 만나게 되었다.
❗ 메모리 초과
처음으로 제출한 코드에 대해서는 메모리 초과의 결과가 나왔다. 함수를 재귀적으로 호출할 때 inorder와 postorder의 벡터를 인자로 주었는데, 이 벡터를 매번 새롭게 할당하여 주도록 만들었던 것이 문제였다.
if (root_index != 0) { //left subtree가 있는경우
vector<int> left_in(inorder.begin(), inorder.begin() + root_index);
vector<int> left_post(postorder.begin(), postorder.begin() + root_index);
preTraversal(left_in, left_post, result);
}
if (root_index != inorder.size() - 1) { //right subtree가 있는경우
vector<int> right_in(inorder.begin() + root_index + 1, inorder.end());
vector<int> right_post(postorder.begin() + root_index, postorder.end()-1);
preTraversal(right_in, right_post, result);
}위 코드처럼 left, right subtree가 있는 경우에 preTraversal 함수를 재귀 호출하였는데, 각 경우에서 left_in, left_post, right_in, right_post라는 이름의 벡터를 계속해서 할당하기 때문에 상당한 메모리 낭비가 발생하였다. 이를 해결하기 위해 처음 입력값으로 받는 inorder와 postorder의 vector를 그대로 인자로 넘기고, 각 subtree에 대한 시작과 끝 index를 추가적으로 인자로 넘기는 방법을 택했다.
각 subtree에 대해 새로운 vector를 할당해주지 않고, index값으로만 조정하는 방법이다.
새로운 할당이 없기 때문에 메모리 사용 측면해서 훨씬 효과적이라고 생각했다.
❗ 시간 초과
이제는 아무 문제 없겠지라고 생각하며 제출하였는데 이번에는 시간 초과를 맞이하게 되었다.
사실 시간 초과에 대해서는 대체 어느 부분이 문제가 되는 것인지 감이 오질 않아서 다른 분들의 코드를 보고 내 코드를 수정하였다. 앞선 메모리 초과를 해결하는 과정에서 처음 input으로 받았던 inorder와 postorder 벡터를 그대로 preTraversal의 인자로 넘겨주기로 했다. 이 값들은 함수가 계속 호출되어도 항상 똑같은 값이므로 굳이 매번 전달할 필요가 없는 것이었다.
따라서 inorder, postorder 벡터를 전역변수로 선언한 후, 별도의 전달 없이 함수 내부에서 사용하면 된다.
알고리즘 해결했더니 메모리가 문제고, 메모리 해결했더니 시간이 초과되고... 깊은 빡침의 연속이었지만 😠 그래도 통과하고 나니까 더욱 뿌듯했따. 또 이번 문제를 통해 불필요한 메모리 사용이나 시간 초과에 대해 경각심을 가지게 된 것 같다 ㅋㅋㅋ 이제는 항상 문제를 풀 때 단순히 통과하는 것만이 아니라 어떻게 하면 더 효율적으로 풀 수 있을지 고민해보는 습관을 들여야겠다! 👍
