[백준][C#] 5639 이진 검색 트리 - 골드5

문제 보기

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

5639번: 이진 검색 트리

 

문제                           

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

• 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
• 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
• 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

 

 

입력                          

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다.

 

 

출력                          

입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.

 

 

풀이방법                 

알고리즘 분류가 그래프 이론, 그래프 탐색, 트리, 재귀로 되어있으나

어째서 분할 정복은 없는건지 모르겠는 문제이다.

 

예제를 보고 생각해보자.

50
30
24
5
28
45
98
52
60

전위 순회라는 것,

그리고 이 트리의 로직

• 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
• 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
• 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

을 보면 이 수열을 루트, 왼쪽 자식, 오른쪽 자식으로 나눌 수 있다.

 

 

왼쪽: 루트보다 작다.

오른쪽: 루트보다 크다.

 

 

루트 다음 노드부터 순회하다가, 루트보다 큰 값을 가진 노드가 나오면

그 노드부터는 오른쪽 아래에 있는 노드들로 간주하면 된다는 것이다.

 

 

루트: 50

왼쪽: 30 24 5 28 45

오른쪽: 98 52 60

 

 

여기서 또  30 24 5 28 45 수열과 98 52 60 수열을 보자.

 

 

루트: 30

왼쪽: 24 5 28

오른쪽: 45

 

루트 98

왼쪽: 52 60

 

...

 

이렇게 나누다 보면 손쉽게 상단의 트리를 구현할 수 있다.

private static void Divide(StringBuilder stringBuilder, int[] nodes, int start, int end)
 {
    if (start >= end)
    	return;

    int i;
    // 루트 다음 인덱스부터 순회
    for(i = start + 1; i < end; i++)
    {
    	// nodes는 입력을 그대로 넣은 int 배열
        // 루트보다 커지면 오른쪽 자식
    	if (nodes[i] > nodes[start])
    		break;
    }

	// 왼쪽 자식을 다음 루트로
    Divide(stringBuilder, nodes, start + 1, i);
    // 오른쪽 자식을 다음 루트로
    Divide(stringBuilder, nodes, i, end);
    
    // 후위 순위니, 왼쪽, 오른쪽 자식의 재귀가 다 끝난 뒤 현재 노드 출력
    stringBuilder.Append(nodes[start]);
    stringBuilder.AppendLine();
}

 

 

 

 

전체 코드

using System;
using System.Text;

namespace BackjoonCodingTest
{
    internal class Program
    {
        static void Main(string[] args)
        {
            using var reader = new System.IO.StreamReader(Console.OpenStandardInput());
            using var print = new System.IO.StreamWriter(Console.OpenStandardOutput());

            int[] nodes = new int[10001];
            int index = 0;

            while(true)
            {
                string input = reader.ReadLine();
                if(input == null || input == "")
                    break;

                nodes[index ++] = int.Parse(input);
            }

            StringBuilder stringBuilder = new StringBuilder();
            Divide(stringBuilder, nodes, 0, index);
            print.WriteLine(stringBuilder.ToString());

            reader.Close();
            print.Close();
        }

        private static void Divide(StringBuilder stringBuilder, int[] nodes, int start, int end)
        {
            if (start >= end)
                return;

            int i;
            for(i = start + 1; i < end; i++)
            {
                if (nodes[i] > nodes[start])
                    break;
            }

            Divide(stringBuilder, nodes, start + 1, i);
            Divide(stringBuilder, nodes, i, end);
            stringBuilder.Append(nodes[start]);
            stringBuilder.AppendLine();
        }
    }
}