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

 

 

 

🧫 문제 분석

 

✔️ 출처

이진 검색 트리 골드 4

 

📖 문제

 

노드가 최대 1만개 이며, 완전 이진 트리가 아니기 때문에 한쪽으로 치우쳐진 트리가 될 수 있다.

이때 최대 인덱스는 iₙ = 2 * iₙ₋₁ + 1 점화식으로 증가하며, 1만번 반복되므로 상상을 초월하는 값이 나오기 때문에  절대로 배열로 해서는 안된다. 

 

1~10까지를 순서대로 넣게되면

1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047로 약 2^11 - 1 까지 커진걸 확인할 수 있다. 

 

즉, 최대 1만개 노드라면 2^10000 - 1 까지 커질 수 있다.

 

따라서 노드 객체를 만들고 좌우에 노드를 연결하는 방식으로 접근해야한다. 

자바에서는 객체의 주소 값을 복사하기 때문에 

. 연산자로 접근해서 객체를 생성하여 연결해주어야한다. 

crruentNode = currentNode.child;
crruentNode = new Node()        // x

currentNode.child = new Node()  // o

 

 

재귀와 반복문 둘다 적용해서 풀었다.

 

그리고 자바로 백준 풀때 입력 종료를 알 수 없다면 입력받은 값을  null check하면 된다. 

---

🔅 문제 풀이 

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

public class Main {

    static class Node {
        int value;
        Node leftNode;
        Node rightNode;

        public Node(int value, Node leftNode, Node rightNode) {
            this.value = value;
            this.leftNode = leftNode;
            this.rightNode = rightNode;
        }
    }
    static StringBuilder sb = new StringBuilder();
    static Node root = null; // 루트 노드

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int sum = 1;
        for (int i = 1; i < 20; i++) {
            sum = sum * 2 + 1;
            System.out.println(sum);
        }

        while (true) {
            String inputNode = br.readLine();
            if (inputNode == null || inputNode.isBlank()) { // 입력이 끝났다면 멈춤
                break;
            }

            int node = Integer.parseInt(inputNode);
//            root = insertNode(node, root); // 재귀
            insertNode(node); // 반복문
        }

        postFix(root);

        System.out.println(sb.toString());

    }

	// 2배 빠름
    private static void insertNode(int nodeValue) {

        if (root == null) {
            root = new Node(nodeValue, null, null);
            return;
        }

        Node next = root;
        while (true) {
            if (next.value > nodeValue) {
                if (next.leftNode == null) {
                    next.leftNode = new Node(nodeValue, null, null);
                    return;
                } else {
                    next = next.leftNode;
                }

            } else {
                if (next.rightNode == null) {
                    next.rightNode = new Node(nodeValue, null, null);
                    return;
                } else {
                    next = next.rightNode;
                }
            }
        }

    }

    private static Node insertNode(int nodeValue, Node nextNode) {

        // 노드가 비어있다면 생성해서 반환
        if (nextNode == null) {
            return new Node(nodeValue, null, null);
        }

        // 현재 노드보다 작다면 left로 이동
        if (nextNode.value > nodeValue) {
            nextNode.leftNode = insertNode(nodeValue, nextNode.leftNode);

            // 현재 노드보다 크다면 right로 이동
        } else if (nextNode.value < nodeValue) {
            nextNode.rightNode = insertNode(nodeValue, nextNode.rightNode);
        }
        return nextNode;
    }

    // 후위 연산
    private static void postFix(Node node) {
        if (node == null) {
            return;
        }

        postFix(node.leftNode);
        postFix(node.rightNode);
        sb.append(node.value).append("\n");
    }

}

 

 

 

❗ 오답노트 / 필요한 지식

1.