N개의 정점을 갖는 이진 트리의 정점에 1부터 N까지의 번호가 중복 없이 매겨져 있다.
이때 중위 순환과 후위 순환이 주어졌을 때, 선위 순환을 구하는 프로그램을 작성해라.
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000)
다음 줄에 중위 순환을 나타내는 N개의 자연수가 주어진다.
그다음 줄에 후위 순환을 나타내는 N개의 자연수가 주어진다.
예제 입력
3
1 2 3
1 3 2
예제 출력
2 1 3
어디서 힌트를 얻을 수 있을까?
우선 중위 순환과 후위 순환이 어떻게 이루어지는지 알 필요가 있다.
위를 보면 알겠지만 후위 순환으로 출력하게 될 경우 루트는 가장 마지막에 존재한다.
이를 통해 루트를 쉽게 찾을 수 있고 루트를 기준으로 '왼쪽'과 '오른쪽' 자식 노드들로 구분할 수 있다.
'왼쪽'과 '오른쪽' 두 키워드를 보면 이것을 루트를 기준으로 분할 할 수 있겠다라는 생각이 든다.
그럼 후위 순환을 통해 기준점인 루트를 찾아주고 중위 순환을 분할하여 찾아낸 루트를 순서대로 출력하면 우리가 찾고자 하는 선위 순환을 출력할 수 있게 된다.
중위 순환에서 루트를 찾는 것은 단순히 반복문을 통해 이룰 수 있지만 다음과 같이 세팅을 하면 상수 시간으로 찾을 수 있다.
int index[N];
index[inOrder[i]] = i;
이 코드는 찾고자 하는 해당 값이 몇 번째 인덱스인지 알려준다.
#include <iostream>
int N;
int inOrder[100001];
int postOrder[100001];
int index[100001];
void solve(int inS, int inE, int poS, int poE, int size)
{
if (inS > inE || poS > poE)
return ;
int root = index[postOrder[poE]];
int left = root - inS;
int right = inE - root;
std::cout << inOrder[root] << ' ';
solve(inS, root - 1, poS, poS + left - 1);
solve(root + 1, inE, poS + left, poE - 1);
}
int main(void)
{
std::cin >> N;
for (int i = 1; i <= N; i++)
{
std::cin >> inOrder[i];
index[inOrder[i]] = i;
}
for (int i = 1; i <= N; i++)
std::cin >> postOrder[i];
solve(1, N, 1, N, N);
std::cout << std::endl;
return 0;
}
https://www.acmicpc.net/problem/2263
백준 2448 - 별 찍기 - 11(C++) (0) | 2023.05.30 |
---|---|
백준 2407 - 조합(C++) (0) | 2023.05.26 |
백준 2206 - 벽 부수고 이동하기(C++) (0) | 2023.05.25 |
백준 2096 - 내려가기(C++) (0) | 2023.05.24 |
백준 1991 - 트리 순회(C++) (2) | 2023.05.24 |