inOrder와 postOrder로 preOrder를 구하는 문제이다.
이 문제를 풀면서 2가지 막히는 부분이 있었다.
첫째 : 알고리즘 자체를 모른다. inorder와 postorder를 어덯게해야 preorder가 나오는지 모르겠다.
둘쨰 : 알고리즘을 코드로 옮길수 없다.
분할정복 알고리즘 : 주어진 문제를 둘 이상의 부분문제로 나눈 뒤 각 문제에 대한 답을 계산하고, 이를 병합해 문제를 해결하는 알고리즘
이진트리를 left, root, right 부분으로 쪼개고, 재귀함수를 활용하여, 쪼갤수 없을때 까지 쪼갠다.
preorder의 순회방식을 이용하여, root->left->right 순서로 값을 출력하면서 순회한다.
void getPreOrder(int inStart, int inEnd, int postStart, int postEnd) {
if (inStart==inEnd || postStart==postEnd)
{
cout << inOrder[inStart] << ' ';
return;
}
int root_index = _index[postOrder[postEnd]];
int leftSize = root_index - inStart;
int rightSize = inEnd - root_index;
cout << inOrder[root_index]<<' ';
if (leftSize>=1)
{
getPreOrder(inStart,root_index-1,postStart,postStart+leftSize-1);
}
if (rightSize>=1)
{
getPreOrder(root_index+1,inEnd,postEnd-rightSize,postEnd-1);
}
return;
}
내가 이문제를 풀면서 가장 시간을 많이 쓴 부분이다. 직접 그림으로 그려가면서 감을 잡는 수 밖에없다.
inorder의 시작과 끝 인덱스
left노드의 시작은 기존 getPreOrder의 시작과 같은 인덱스이므로, inStart = inStart(기존)
root_index의 앞부분까지가 inorder의 인덱스이므로, inEnd = root_index-1
postorder의 시작과 끝 인덱스
postStart도 마찬가지로 동일 postStart = postStart(기존)
postEnd는 leftSize값과 관련이있다. postStart+leftSize-1이다.
inorder의 시작과 끝 인덱스
root뒤부터이므로, inStart = root+1
끝은 동일하므로, inEnd = inEnd(기존)
postorder의 시작과 끝 인덱스
끝지점은 구하기가 쉽다. 기존 끝지점은 root값에 사용되므로, postEnd = postEnd(기존)-1
거기에 사이즈를 빼주면 시작점이 된다. postStart = postEnd(기존)-rightSize
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <math.h>
#include <string>
#include <string.h>
#include <queue>
using namespace std;
#define endl "\n"
#define MAX 100000+1
int n;
int inOrder[MAX];
int postOrder[MAX];
int _index[MAX];
void input() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
//ifstream cin; cin.open("input.txt");
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> inOrder[i];
_index[inOrder[i]] = i;
}
for (int i = 1; i <= n; i++)
{
cin >> postOrder[i];
}
}
void getPreOrder(int inStart, int inEnd, int postStart, int postEnd) {
if (inStart==inEnd || postStart==postEnd)
{
cout << inOrder[inStart] << ' ';
return;
}
int root_index = _index[postOrder[postEnd]];
int leftSize = root_index - inStart;
int rightSize = inEnd - root_index;
cout << inOrder[root_index]<<' ';
if (leftSize>=1)
{
getPreOrder(inStart,root_index-1,postStart,postStart+leftSize-1);
}
if (rightSize>=1)
{
getPreOrder(root_index+1,inEnd,postEnd-rightSize,postEnd-1);
}
return;
}
int main()
{
input();
getPreOrder(1, n, 1, n);
}
https://donggoolosori.github.io/2020/10/15/boj-2263/ 전체적인 풀이 및 getPreOrder의 인수
https://sectumsempra.tistory.com/93 분할정복 알고리즘의 원리