[PS] 백준 5639번: 이진 검색 트리

|

문제

내가 이해한 문제 내용

BST의 전위 순회가 나열될 때 그걸 바탕으로 후위순회가 어떻게 동작하는지 짜라.

접근 방식

전위순회를 입력받아서 BST를 생성하고 후위순회를 돌렸다. → 수정: 받아서 곧바로 후위순회 돌림

어려웠던 점 & 배운 점

BST를 짜다가 포인터부분에서 계속 동작을 안해서 난감했는데 알고보니 while 안에서 노드 객체를 생성해서 계속 사라진 것이었다. 즉, 주소값을 넘겨주어도 사라지니 NULL값이 된 것… 나의 멍청했던 질문을 보자.

또 입력을 받을 때 컴파일러에게 어떻게 종료시키는지 의문이 들었는데 질문란을 보니 scanf가 입력종료값을 입력받으면 EOF=-1를 리턴한다고 해서 그걸 종료 플래그로 잡았다. 입력종료값은 윈도우에서 Ctrl+Z이다.

수정: 다시 공부하다가 이게 BST를 생성하는게 아니라 전위순회가 들어온대로 후위순회를 돌리는 문제였다;; 전위순회가 루트-왼쪽-오른쪽 순이고 후위순회가 왼쪽-오른쪽-루트니까 들어오는 값을 기준으로 왼쪽과 오른쪽을 나누어서 원래 후위순회를 돌리는 방식처럼 재귀를 돌리면 간단한문제….너무 단순하게 생각하지 말자.

시간복잡도

각 노드를 한번씩 방문하니까 $O(n)$이다.

코드

#include <cstdio>

int a[10001];

void post(int s, int e)
{  
    if(s>e) return;
    int i;
    for(i=s+1; i<=e; i++)
        if(a[i]>a[s]) break;
    
    post(s+1,i-1);
    post(i,e);
    printf("%d\n",a[s]);
}

int main(void)
{
    int i=0;
    while(scanf("%d",&a[i++])!=EOF);
    post(0,i-2);
    return 0;
}