[C++] BAEKJOON 2263 트리의 순회

https://www.acmicpc.net/problem/2263

2263번: 트리의 순회

분할정복 을 사용하여 문제를 해결하였습니다.

먼저 트리의 순회하는 3가지 방법에 대해서 알아야합니다.

inorder : Left —> root —> Right

postorder : Left —> Right —> root

preorder : root —> Left —> Right

inorder 와 postorder 가 주어졌을 때 preorder 를 구하기 위해선 아래와 같은 과정을 거칩니다.

1. postorder의 맨 뒤가 root 이므로 root 가 무엇인지 찾을 수 있습니다.
2. preorder 는 root 를 우선적으로 출력하므로 이를 출력합니다.
3. inorder 에서 root 를 기준으로 Left 와 Right 로 나눌 수 있습니다.
4. 나눈 Left 와 Right 를 에 대해서 각각 1번부터 반복합니다.

 

이를 solve 함수를 통해 분할정복을 통해 구현하며 inorder 의 시작, 끝 위치와 postorder 의 시작, 끝 위치를 함수의 인자로 받게 됩니다.

#include <iostream>

using namespace std;

int inorder[100000];  // L -> root -> R
int postorder[100000]; // L -> R -> root
int pos[100001];
//preorder : root -> L -> R

void solve(int in_start, int in_end, int po_start, int po_end){
    if (in_start > in_end || po_start > po_end) return;
    // postorder의 맨 뒤가 root 이므로 root 가 무엇인지 찾을 수 있습니다.
    int root = postorder[po_end];
		//  preorder 는 root 를 우선적으로 출력하므로 이를 출력합니다.
    cout << root << " ";
    int index = pos[root];
    int length = index-in_start;
	  //  inorder 에서 root 를 기준으로 Left 와 Right 로 나눌 수 있습니다.
    solve(in_start,index-1,po_start,po_start+length-1);
    solve(index+1, in_end,po_start+length, po_end-1);
}
int main(int argc, const char * argv[]) {

    int n;
    cin >> n;

    for (int i=0;i<n;i++){
        cin >> inorder[i];
    }
    for (int i=0;i<n;i++){
        cin >> postorder[i];
    }
    for (int i=0;i<n;i++){
        // pos 배열은 해당 값이 몇 번째에 위치하는지 O(1) 만에 구할 수 있다.
        pos[inorder[i]] = i;
        // ex) pos[4] = 0; : 4 값은 inorder 배열에서 0번째에 위치
    }
    

    solve(0,n-1,0,n-1);
    return 0;
}

 

시간복잡도

트리의 총 노드 수가 N 일 때, preorder 는 N 번 출력을 해야합니다. 이는 solve 함수가 총 N 번 호출됨을 의미합니다. solve 함수 내부적으로는 O(1) 의 복잡도를 가집니다.

int index = pos[root];

root 가 inorder 에서 어디에 위치하는지 찾기 위해서 O(N) 에 해당하는 순회를 거쳐야 하지만 기존에 pos 배열을 통해 해당 값이 어디에 위치하는지 미리 저장을 해두었습니다.

    for (int i=0;i<n;i++){
        // pos 배열은 해당 값이 몇 번째에 위치하는지 O(1) 만에 구할 수 있다.
        pos[inorder[i]] = i;
        // ex) pos[4] = 0; : 4 값은 inorder 배열에서 0번째에 위치
    }

이로서 전체적으로 O(N) * O(1) = O(N) 의 시간복잡도로 문제를 해결할 수 있습니다.