문제 링크 : https://www.acmicpc.net/problem/15805
이 문제에서는 어느 트리가 있을 때, input으로 ..
1. 그것이 중위순회였는지, 후위순회였는지 등을 알 수 없다.
2. 이진트리라는 보장이 없다. 예제에서 조차 이진트리가 아니다.
따라서 우리는 중위순회, 후위순회, 전위순회를 해보며 문제를 해결할 수 없다.
문제를 풀기 위한 힌트는, 트리가 순회를 할때, 어느 방향으로(왼,오, .. ) 가던지 다른 서브트리로 갈 때엔 이전 서브트리의 root 를 지나야 한다는 것이다.
이 방안에 착안하여, 어느 노드를 방문 했을 때, visited 배열로 방문하였다고 표시하고, 만약 이전에 방문하지 않았던 노드라면, 그 노드 이전의 노드(스택으로 관리함) 를 부모노드로 정하는 것으로 풀었다.
소스코드 :
이 문제에서는 어느 트리가 있을 때, input으로 ..
1. 그것이 중위순회였는지, 후위순회였는지 등을 알 수 없다.
2. 이진트리라는 보장이 없다. 예제에서 조차 이진트리가 아니다.
따라서 우리는 중위순회, 후위순회, 전위순회를 해보며 문제를 해결할 수 없다.
문제를 풀기 위한 힌트는, 트리가 순회를 할때, 어느 방향으로(왼,오, .. ) 가던지 다른 서브트리로 갈 때엔 이전 서브트리의 root 를 지나야 한다는 것이다.
이 방안에 착안하여, 어느 노드를 방문 했을 때, visited 배열로 방문하였다고 표시하고, 만약 이전에 방문하지 않았던 노드라면, 그 노드 이전의 노드(스택으로 관리함) 를 부모노드로 정하는 것으로 풀었다.
소스코드 :
| 
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 
54 
55 
56 
57 
58 | 
#include <iostream> 
#include <vector> 
#include <algorithm> 
using namespace std; 
int n; 
// 기방문 여부 관리 배열 
bool *visited; 
// 이전에 방문한 적 있는가? 
bool Checker(vector<int> & v, int offset) { 
    for (int i = 0; i < v.size(); i++) { 
        if (offset == v[i]) { 
            return true; 
        } 
    } 
    return false; 
} 
int main() { 
    cin.tie(0); 
    ios_base::sync_with_stdio(false); 
    cin >> n; 
    vector<int> v(n); 
    vector<int> answer(n, -1); 
    for (int i = 0; i < n; i++) { 
        cin >> v[i]; 
    } 
    // root 
    answer[v[0]] = -1; 
    vector<int> base; 
    visited = new bool[n](); 
    visited[v[0]] = true; 
    base.push_back(v[0]); 
    int answerCnt = 1; 
    for (int i = 1; i < n; i++) { 
        // 방문안했었다면 이전 노드를 부모로 설정 
        if (!Checker(base, v[i])) { 
            answer[v[i] ] = base.back(); 
            answerCnt++; 
        } 
        base.push_back(v[i]); 
        visited[v[i]] = true; 
    } 
    cout << answerCnt << endl; 
    for (int i = 0; i < answerCnt; i++) { 
        cout << answer[i] << ' '; 
    } 
} | cs | 
댓글
댓글 쓰기