트리 나라 관광 가이드 - 15805

//15805 - 트리 나라 관광 가이드
 
#include <iostream>
using namespace std;
 
int N;
int arr[200000], parent[200000];
bool visit[200000];
 
int main()
{
    cin >> N;
    for(int i = 0; i<N; ++i)
        cin >> arr[i], visit[i] = false;
    int ans = 0;
    int child = -1;
    for(int i = 0; i<N; ++i)
        if(!visit[arr[i]])
            ++ans, visit[arr[i]] = true, child = arr[i];
        else
            parent[child] = arr[i], child = arr[i];
    
    parent[child] = -1;
 
    cout << ans << "\n";
    for(int i = 0; i<ans; ++i)
        cout << parent[i] << " ";
}

 

 

 

 

 

 

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

15805번: 트리 나라 관광 가이드

 

 

 

 

 

 

트리 나라 관광 가이드

트리의 inorder traversal 순서가 주어졌을때  각 노드의 부모 노드를 출력하는 문제입니다.

inorder traversal의 특성인 특정 노드를 발견하면, 다시 특정 노드가 나올때까지 특정노드의 모든 자식을 방문하고 돌아온다는 것을 이욯하면 됩니다.