문제링크 : https://www.acmicpc.net/problem/2263
이 문제는 트리의 성질을 이용해서 풀어야 하는 문제이다.
중위순회, 후위순회 순서가 주어진다.
이때, 후위순회에서 맨 마지막에 있는 원소는 전위순회에서는 맨 처음 방문하는 원소이다.
따라서 이 성질을 이용하도록 하자.
후위순회의 맨 마지막 원소가 중위순회에서 몇번째 인덱스인지 찾고
중위순회 배열에서
1. 첫번째 인덱스 ~ 찾은 인덱스,
2. 찾은인덱스 ~ 마지막 인덱스
로 분할 한다. 그 이유는 중위는 말 그대로 중간에 거친 원소이니, 좌 우로 나눌수 있기 때문이다.
중위순회 배열을 나눴다면 후위순회 배열도 나누어야 한다.
후위순회도
1. 후위 배열의 첫번째 인덱스 ~ 찾은인덱스 - 중위순회에서의 첫 인덱스 - 1
2. 후위 배열의 첫번째 인덱스 ~ 마지막 인덱스 -1 을 해줘야 한다.
소스코드 :
이 문제는 트리의 성질을 이용해서 풀어야 하는 문제이다.
중위순회, 후위순회 순서가 주어진다.
이때, 후위순회에서 맨 마지막에 있는 원소는 전위순회에서는 맨 처음 방문하는 원소이다.
따라서 이 성질을 이용하도록 하자.
후위순회의 맨 마지막 원소가 중위순회에서 몇번째 인덱스인지 찾고
중위순회 배열에서
1. 첫번째 인덱스 ~ 찾은 인덱스,
2. 찾은인덱스 ~ 마지막 인덱스
로 분할 한다. 그 이유는 중위는 말 그대로 중간에 거친 원소이니, 좌 우로 나눌수 있기 때문이다.
중위순회 배열을 나눴다면 후위순회 배열도 나누어야 한다.
후위순회도
1. 후위 배열의 첫번째 인덱스 ~ 찾은인덱스 - 중위순회에서의 첫 인덱스 - 1
2. 후위 배열의 첫번째 인덱스 ~ 마지막 인덱스 -1 을 해줘야 한다.
소스코드 :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> in;
vector<int> post;
vector<int> Slice(const vector<int>& v, int a, int b) {
return vector<int>(v.begin() + a, v.begin() + b);
}
int cnt = 0;
void Recursive(int s1, int e1, int s2, int e2) {
if (s1 > e1 || e2 < s2) {
return;
}
cout << post[e2] << ' ';
int find = post[e2];
for (int i = s1; i <= e1; i++) {
if (find == in[i]) {
find = i;
break;
}
}
Recursive(s1, find - 1, s2, s2 + find - s1-1);
Recursive(find + 1, e1, s2+(find - s1) , e2- 1);
}
int main() {
int n;
cin >> n;
in.resize(n , 0);
post.resize(n , 0);
cin.clear();
cin.ignore();
for (int i = 0; i < n; i++) {
cin >> in[i];
}
cin.ignore();
for (int i = 0; i < n; i++) {
cin >> post[i];
}
Recursive(0, post.size() - 1, 0, post.size()-1);
return 0;
}
| cs |
댓글
댓글 쓰기