(Java) 백준 5639 - 이진 검색 트리

많이 어려움을 겪었던 문제였다.

보통 다른 문제들은 입력값 N을 주어 몇 번 입력되는지 알려주는데 

이 문제는 N이 없어서 고생을 많이 했다.

while문으로 입력값이 없으면 멈추게 하려고 시도하고 IDE에서 디버깅을 했는데 잘 되지 않았다.

입력문을 처리하려고 한 시간을 넘게 시도했지만 계속 실패해서

결국 검색을 통해 다른 분들은 어떻게 풀었는지 참고했는데

나랑 똑같은 방법으로 풀었다........

설마 IDE가 문제인가 싶어서 디버깅 없이 답안을 제출하니 맞았다.

트리를 연습하려고 문제를 풀었는데 입력값 처리만 고민해서 허무했다.

 

이 문제는 입력값으로 트리로 만들 수만 있다면 간단한 문제다.

트리를 만들 수 있다면 후위 순회 메서드는 금방 작성할 수 있기 때문이다.

다만 트리를 만드는 게 그렇게 쉽지는 않았다.

클래스를 만들어서 트리 구조를 구현하는 게 익숙하지도 않고 재귀적으로 생각해야 하는 게 있어서

앞으로 트리 문제를 풀 때 클래스를 만들어서 푸는 연습을 해봐야겠다.

---

최종 코드

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

// IDE로는 Input을 중단할 수 않아서 디버깅 불가
public class Main {
    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 input;
        while ((input = br.readLine()) != null) {
            root.insert(Integer.parseInt(input));
        }

        // 후위 순회
        preOrder(root);

    }

    // 후위 순회 메서드
    static void preOrder(Node node) {
        if (node == null) return;
        preOrder(node.left);
        preOrder(node.right);
        System.out.println(node.num);
    }

    // 트리 클래스
    static class Node {
        int num;

        Node left, right;

        // 생성자
        Node(int num) {
            this.num = num;
        }

        // 노드 추가 메서드
        void insert(int num) {
            // 입력 num이 현재 노드보다 작다면
            if (num < this.num) {
                // 자식 노드가 없으면 새로 생성
                if (this.left == null) {
                    this.left = new Node(num);
                    // 자식 노드가 있다면 탐색후 추가
                } else {
                    this.left.insert(num);
                }
            } else {
                if (this.right == null) {
                    this.right = new Node(num);
                } else {
                    this.right.insert(num);
                }
            }
        }
    }
}