백준 2263번 : 트리의 순회

문제 접근

---

inorder 의 첫번째 원소가 가장 왼쪽에 있는 노드를 가리키듯이, postorder 의 마지막 원소는 root 를 가리킨다. 이를 이용해서 inorder 에서 root 를 찾고, 왼쪽, 오른쪽을 나눠서 재귀로 찾고 preorder 에 끼워 넣는 방식을 생각했다.

 

처음에 함수의 인자는 4개 였는데, 코드를 작성하다보니 변수가 무슨 역할을 하는지도 헷갈리고, 코드가 복잡해졌다. 그래서 틀만 남긴 뒤 다 지우고, 각 변수의 역할을 지정한 뒤 깔끔하게 코드를 구현했다.

 

AC 되고 다른 코드들을 보니, 내 코드보다 빠르게 돌아가서 확인해봤다. 다른 코드들은 이진 트리의 정점에 1 부터 n 까지 중복 없이 매겨져있다는 것을 이용해서 'arr[정점번호] = 순서' 와 같이 배열을 만들어 find 할 필요 없이 구현했다. 내 코드에서 시간을 더 줄일 방법이 없을까 고민하던 중, vector에서 find 의 시간 복잡도는 O(n) 이고, list 에서는 O(1) 이라는 게 떠올라서 list 로 구현해보려고 했는데 iterator 가 Rnad Access 가 아니여서 내 코드에서는 이용하기 힘들었다.

 

주의할 점!

1. 코드를 작성할 때, 구조화하고 체계적으로 계획을 세워 작성하자.

2. 각 변수와 함수의 할 일을 명확히 하자.

3. 머리로 미리 논리를 돌려보는 습관을 가지자.

 

 

문제 코드

---

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

// postorder 는 끝에 있는 거만 빼면 돼서 stack 을 사용했다.
vector<int> inorder, preorder;
stack<int> postorder;

// prePos 는 preorder 에서 insert 할 위치를 가리킨다.
// start, end 는 find 할 범위를 가리킨다.
void build_pre(int prePos, int start, int end)
{
	if(postorder.empty())
		return;
	
	if(start==end)
		return;
	
	int root = postorder.top();
	postorder.pop();
	
	int pos = find(inorder.begin()+start, inorder.begin()+end, root) - inorder.begin();
	
	if(pos==end)
		return;
	
	preorder.insert(preorder.begin()+prePos, root);
	
	build_pre(prePos+1, pos+1, end);
	
	build_pre(prePos+1, start, pos);
}

int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n, input;
	
	cin>>n;
	
	for(int i=0; i<n; ++i)
	{
		cin>>input;
		inorder.push_back(input);
	}
	
	for(int i=0; i<n; ++i)
	{
		cin>>input;
		postorder.push(input);
	}
	
	build_pre(0, 0, n);
	
	for(int i=0; i<preorder.size(); ++i)
		cout<<preorder[i]<<' ';
	cout<<'\n';
}

 

개선한 코드

---

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int n;

vector<int> inorder, preorder;
stack<int> postorder;
vector<int> seq(n);

void build_pre(int prePos, int start, int end)
{
	if(postorder.empty())
		return;
	
	if(start==end)
		return;
	
	int root = postorder.top();
	postorder.pop();
	
	if(root<start || root>=end)
		return;
	
	int pos = seq[root];
	
	preorder.insert(preorder.begin()+prePos, root);
	
	build_pre(prePos+1, pos+1, end);
	
	build_pre(prePos+1, start, pos);
}

int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int input;
	
	cin>>n;
	
	for(int i=0; i<n; i++)
	{
		cin>>input;
		inorder.push_back(input);
        // 이 부분에서 segment dump 뜬다. 왜지?
		seq[input] = i;
	}
	
	for(int i=0; i<n; ++i)
	{
		cin>>input;
		postorder.push(input);
	}
	
	build_pre(0, 0, n);
	
	for(int i=0; i<preorder.size(); ++i)
		cout<<preorder[i]<<' ';
	cout<<'\n';
}

 

테스트 케이스

---

13
1 3 2 4 5 6 7 8 9 10 11 12 13
1 2 3 6 5 4 9 8 11 13 12 10 7

ans : 7 4 3 1 2 5 6 10 8 9 12 11 13