문제

문제 링크

문제 접근

  • 이 문제는 트리를 순회하는 3가지 방법인 inorder, preorder, postorder traverse의 특징을 잘 이해해야 풀 수 있는 문제입니다.
  • inorder는 left - root - right 순으로
  • postorder는 left - right - root 순으로
  • preorder는 root - left - right 순으로 순회하게 됩니다.
  • 이 때 발견되는 특징은 postorder는 항상 root가 맨끝에 오기 때문에 postorder의 맨끝은 root 라는 것을 알 수 있습니다.
  • 그리고 inorder에서는 root를 기준으로 left와 right를 찾을 수 있습니다.

preorder 함수

  • 일단 preorder 함수는 post와 inorder의 범위를 받습니다.
  • preorder는 root를 출력하기 때문에 먼저 root를 출력해줍니다.
  • inorder에서 root 노드의 인덱스를 찾아주고 이를 기준으로 왼쪽은 left 오른쪽은 right로 여겨줍니다.
  • 그후 left와 right 각각에 대해서 또 다시 preorder traverse를 진행합니다.
  • 이 때, left와 right가 없는 경우에는 traverse하지 않습니다.

효율성 증대

  • 초기에는 inorder 어레이에도 처음부터 하나씩 넣어주고 root의 위치를 찾을 때 처음부터 끝까지 찾게 했습니다.
  • 하지만 inorder 어레이에 각 원소의 index를 넣어주게 되면 root의 index를 바로 찾을 수 있기 때문에 탐색 시간이 훨 짧아지는 것을 볼 수 있었습니다!

코드

#include <cstdio>

int n, temp, post[100001], in[100001];

void pre(int ps, int pd, int is, int id){
    int root = post[pd];
    printf("%d ", root);
    int lcnt = in[root] - is - 1;
    if(in[root] != is) pre(ps, ps + lcnt, is, in[root] - 1);
    if(in[root] != id) pre(ps + lcnt + 1, pd - 1, in[root] + 1, id);
}

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d", &temp);
        in[temp] = i;
    }
    for(int i = 0; i < n; i++)scanf("%d", &post[i]);
    pre(0, n - 1, 0, n - 1);
}

느낀점

  • 오랜만에 풀다보니 안풀리던 것도 풀리게 되어서 만조쿠!
  • 인덱스를 저장하는 것과 같은 참신함이 언젠간 내머리에도 있기를 ㅎㅎ