[백준] 5639번 : 이진 검색 트리 Gold5(골드5) - JAVA[자바]

[Gold V] 이진 검색 트리 - 5639

문제 링크

성능 요약

메모리: 16088 KB, 시간: 376 ms

분류

그래프 이론, 그래프 탐색, 재귀, 트리

제출 일자

2024년 1월 10일 21:12:46

문제 설명

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

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

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

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

입력

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

출력

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

접근 방식

1. 전위순회(VLR)로 입력 받은 그래프의 원본을 만든다.

2. 그래프를 통해서 후위순위한 결과를 반환한다.

 

그래프의 원본을 만드는 과정

값을 입력 받았을 때 루트보다 작다면 왼쪽, 크다면 오른쪽 서브트리인 이진트리이다.

1. 루트로부터 값을 입력 받은 뒤 현재 값보다 크다면,오른쪽 작다면 왼쪽으로 보낸다.

2. 다음 연결 노드가 Null이라면 연결해준다.

// 노드 값 입력 받음
            int node = Integer.parseInt(tmp);
            // 루트부터 시작하여 현재 입력 값을 넣을 위치를 찾는다.
            // 즉 그래프를 먼저 만들어준다.
            Node pos = root;
            while (true) {
                // 값이 현재 값보다 작다면 왼쪽
                if (pos.value > node) {
                    // 만약 왼쪽 노드가 존재하지 않는다면 그 자리에 입력 값을 노드로 위치시킨다.
                    if (pos.left == null) {
                        pos.left = new Node(node);
                        break;
                    }
                    // 존재한다면 pos를 pos.left로 갱신한다.
                    else {
                        pos = pos.left;
                    }
                }
                // 현재 값보다 크다면 오른쪽
                else {
                    // 오른쪽 노드가 존재하지 않는다면 그 자리에 입력 값을 노드로 위치 시킨다.
                    if (pos.right == null) {
                        pos.right = new Node(node);
                        break;
                    }
                    // 존재한다면 pos를 pos.left로 갱신한다.
                    else {
                        pos = pos.right;
                    }
                }
            }
        }

 

후위순위(LRV)로 결과를 만드는 과정

1. 루트부터 시작하여 확인한다.

2. 왼쪽 노드를 확인 후 연결되어 있다면 재귀 호출(Left Node)

3. 오른쪽 노드 확인 후 연결되어 있다면 재귀 호출(Right Node)

4. 현재 노드의 값을 StringBuilder에 넣어준다.(V Node)

// 후위순위로 출력
    private static void LRV(Node node) {
        // 왼쪽 노드가 null이 아니라면(연결되어 있다면) 재귀 호출
        if (node.left != null) {
            LRV(node.left);
        }
        // 오른쪽 노드가 null이 아니라면(연결되어 있다면) 재귀 호출
        if (node.right != null) {
            LRV(node.right);
        }
        // 시간을 단축시키기 위해 현재 노드의 값을 출력하는 것이 아닌 StringBuilder에 넣어준다.
        sb.append(node.value).append("\n");
    }

 

전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

class Main {
    // 그래프를 만들기 위한 노드 클래스
    static class Node {
        int value;
        Node left, right;

        Node(int value) {
            this.value = value;
        }
    }
    // 출력하는 시간을 줄이기 위한 StrignBuilder
    static StringBuilder sb = new StringBuilder();
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 처음 입력 받은 값은 무조건 루트 노드이다. -> 전위순회이기때문에
        Node root = new Node(Integer.parseInt(br.readLine()));

        String tmp;
        while (true) {
            // 입력 받은 값이 null이거나 비어있다면 EOF이므로 종료
            tmp = br.readLine();
            if (tmp == null || tmp.isEmpty()) {
                break;
            }
            // 노드 값 입력 받음
            int node = Integer.parseInt(tmp);
            // 루트부터 시작하여 현재 입력 값을 넣을 위치를 찾는다.
            // 즉 그래프를 먼저 만들어준다.
            Node pos = root;
            while (true) {
                // 값이 현재 값보다 작다면 왼쪽
                if (pos.value > node) {
                    // 만약 왼쪽 노드가 존재하지 않는다면 그 자리에 입력 값을 노드로 위치시킨다.
                    if (pos.left == null) {
                        pos.left = new Node(node);
                        break;
                    }
                    // 존재한다면 pos를 pos.left로 갱신한다.
                    else {
                        pos = pos.left;
                    }
                }
                // 현재 값보다 크다면 오른쪽
                else {
                    // 오른쪽 노드가 존재하지 않는다면 그 자리에 입력 값을 노드로 위치 시킨다.
                    if (pos.right == null) {
                        pos.right = new Node(node);
                        break;
                    }
                    // 존재한다면 pos를 pos.left로 갱신한다.
                    else {
                        pos = pos.right;
                    }
                }
            }
        }

        // 루트노드부터 시작
        LRV(root);
        System.out.println(sb);
    }

    // 후위순위로 출력
    private static void LRV(Node node) {
        // 왼쪽 노드가 null이 아니라면(연결되어 있다면) 재귀 호출
        if (node.left != null) {
            LRV(node.left);
        }
        // 오른쪽 노드가 null이 아니라면(연결되어 있다면) 재귀 호출
        if (node.right != null) {
            LRV(node.right);
        }
        // 시간을 단축시키기 위해 현재 노드의 값을 출력하는 것이 아닌 StringBuilder에 넣어준다.
        sb.append(node.value).append("\n");
    }
}