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

해결 방법

EOF를 만나기 전 까지 입력받기

while(cin>>a) {/* 입력받는동안 할 일 */}

요런식으로 하면 된다

VLR to LRV

처음엔 직접 트리를 만들어서 후위순회 하려고 했었다.. 하지만 그게 잘 안됐음^.ㅜ
그래서 다른 방법으로 시도했다.

• 주어진 전위순회에서, 노드와 왼쪽 서브트리, 오른쪽 서브트리를 분리할 수 있다.
  
  • 맨 앞 노드 == 방문 노드
  • 오른쪽 서브트리 시작점 == 방문노드보다 큰 노드 중, 가장 처음
  • 왼쪽 서브트리 == 방문노드 + 1 ~ 오른쪽 서브트리 시작점 - 1
• 분리한 노드 / 왼쪽 / 오른쪽을 👉 왼쪽 / 오른쪽 / 노드 순서로 바꿔주면 된다.
  • 분리된 왼쪽 / 오른쪽 안에서도 또 노드 / 왼 / 오를 구해야하니까 이건 재귀로 해결!

소스 코드

#include <iostream>
#include <vector>
using namespace std;
#define pii pair<int, int>

vector<int> arr;

void preToPost(int node, int bound){ //VLR to LRV
  //오른쪽 시작 노드 찾기
  int right = node + 1;
  while(right<=bound && arr[right]<arr[node])
    ++right;
  //왼쪽 순회 L
  int left = node + 1;
  if(left<right) preToPost(left,right-1);
  //오른쪽 순회 R
  if(right<=bound) preToPost(right,bound);
  //노드 방문 V
  cout<<arr[node]<<"\n";
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);

  int input;
  while(cin>>input) arr.push_back(input);

  int size = arr.size();
  preToPost(0,size-1);
}

제출 결과

노드를 출력하지 않고 노드의 인덱스를 출력해서 틀렸었다 헤헤