[백준] 2957번 : 이진 탐색 트리 - 자바(JAVA)

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

2957번: 이진 탐색 트리

 

문제 해석

1보다 크거나 같고, N보다 작거나 같은 수 N개가 한 번씩 등장하는 수열이 주어집니다.

이때 이진트리를 구성하면 왼쪽 서브트리에는서브 트리에는 X보다 작은 수, 오른쪽 서브 트리에는 X보다 큰 수만 저장되어 있어야 합니다.

첫 번째 수를 루트로 놓고 다 머지 수들을 순서대로 삽입하고자 합니다.

이때 함수안에 C라는 카운터를 1씩 증가시키는 구문이 존재하는데 트리에 삽입된 후에 카운터 C값을 한 줄에 하나씩 출력하세요

 

예제 입력을 보면서 해석을 해보겠습니다.

4
1
2
3
4

처음 4는 N의 크기를 말합니다.

다음 N개의 줄은 수열의 수가 차례 되로 주어집니다.

 

처음에는 1이 루트노드가 됩니다. C는 0이 출력됩니다(insert에 들어가지 않기 때문에)

 

그다음에는 insert(2, root)가 호출됩니다. 

X(2)가 노드 N(1) 보다 크기 때문에 첫 번째 else분기로 내려가고 N의 오른쪽 자식이 없기 때문에 X를 포함하는 새 노드를 만든 뒤 N의 오른쪽 자식으로 갑니다.

재귀적으로 insert를 호출하지 않았기 때문에 C는 1이 출력됩니다.

 

그다음에는 insert(3,root)가 호출됩니다.

이번에도 X(3)이 노드 N(1) 보다 크기 때문에 첫 번째 else분기로 내려가고 N의 오른쪽 자식이 이번에는 존재하기 때문에 insert(3, Node(2))를 호출합니다. 이후에는 값이 들어가게 되고 C는 2가 더해진 3이 출력됩니다.

 

그다음에 insert(4,root)가 호출되면?

이번에도 현재 입력된 수중에 제일 큰 수가 들어왔으니 오른쪽으로 이동(C++), 오른쪽으로 이동(C++), 원래 들어오면서(C++) 총 3이 더해진 6이 출력됩니다.

 

따라서 예제 출력이 다음과같이 나오게 됩니다.

0
1
3
6

 

문제 풀이 전 설계

Node클래스를 만들고 int value, Node left , Node right로 설계합니다.

int형을 써도 1~30만 범위에 오버플로우가 발생하지 않습니다.

이후에는 주어진 문제에 따라 착실하게 구현해보려고 하며 StringBuilder에 담아 한꺼번에 출력하고자 합니다.

 

문제 풀이 하면서

간단하게 이진트리를 구성해서 해결하려고 했으나 시간 초과가 났습니다.

조금 생각해보니 30만 개를 입력하면서 최악의 경우에는 선형 자료구조의 형태를 띠게 되고 O(N^2)이 나오면서 시간 초과가 발생했습니다.

 

TreeSet 자료구조를 활용하는 문제였습니다.

TreeSet은 이진 탐색 트리 구조로 데이터를 저장하는 클래스입니다.

부모 노드보다 작은 값을 가지는 노드는 왼쪽 자식으로, 큰 값을 가지는 노드는 오른쪽 자식으로 배치하여 데이터의 추가나 삭제 시 트리가 한쪽으로 츼우쳐지지 않도록 균형을 맞춰줍니다.

 

여기서 드는 생각은 원래는 그냥 트리 형태였는데 Balnced Tree로 만들면 문제에서 원하는 답을 제공할 수 있을까?입니다.

 

원래는 선형구조라면 insert가 여러 번 호출되어야 하겠지만 Balnced Tree는 그렇지 않게 됩니다.

 

그래서 여기서는 lower , heigher 메서드를 활용합니다.

lower 메서드는 해당 객체와 연결된 가장 작은 객체를 찾아줍니다.

heigher는 해당 객체와 연결된 가장 큰 객체를 찾아줍니다.

주의할 점은 x보다 큰 값이 없거나 작은 값이 없는 경우에는 null을 반환해줍니다.

 

예를 들어 key가 5인 이진트리의 왼쪽 자식은 4, 오른쪽 자식은 7이라고 했을 때 lower(5)는 4를 반환합니다.

heigher (5)는 7을 반환합니다.

 

따라서 이 특성을 이용해서 높이를 일일이 다 구해주고 나면 insert는 높이의 수만큼 호출되므로 답을 도출할 수 있습니다.

 

또한 TreeSet은 Red-black tree 해당 트리가 어떻게 균형 트리를 유지하는지를 알아야 이 문제를 해결할 수 있습니다.

 

다음 링크를 통해서 

https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

Red/Black Tree Visualization

 

정답 코드

import java.util.*;
import java.io.*;

public class Main_2957_이진탐색트리정답 {


        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int n = Integer.parseInt(br.readLine());
            long answer=0;
            //깊이를 저장하기 위한 배열
            int[] depth = new int[n+2];
            //초기값 세팅
            depth[0]=-1;
            depth[n+1]=-1;
            //TreeSet 선언
            TreeSet<Integer> tree = new TreeSet<>();
            //초기값을 위해서 0,N+1설정
            tree.add(0);
            tree.add(n+1);

            StringBuilder sb = new StringBuilder();
            for(int i=0;i<n;i++){
                Integer e = Integer.parseInt(br.readLine());
                //처음에는 tree.lower(e) = 0, tree.higher(e) = N+1  즉, Math.max(-1,-1) + 1 = 0
                System.out.println(tree.lower(e) + " " + tree.higher(e));
                depth[e] = Math.max(depth[tree.lower(e)],depth[tree.higher(e)])+1;
                tree.add(e);
                answer+=depth[e];
                sb.append(answer+"\n");
            }
            System.out.println(sb.toString());
        }

}

 

기존의 접근방법 : 실패(시간 초과)

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

public class Main_2957_이진탐색트리 {

    static int count;

    static class Node {
        int value;
        Node left;
        Node right;

        public Node(int value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }

        public void insert(int inputValue, Node node) {
            count++;
            //inputValue가 현재값보다 작다면
            if (node.value > inputValue) {
                //현재값의 왼쪽자식이 없다면
                if (node.left == null) {
                    node.left = new Node(inputValue, null, null);
                } else {
                    insert(inputValue, node.left);
                }
            } else {
                //현재값의 오른쪽자식이 없다면
                if (node.right == null) {
                    node.right = new Node(inputValue, null, null);
                } else {
                    insert(inputValue, node.right);
                }
            }
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int length = Integer.parseInt(br.readLine());
        int[] numbers = new int[length];
        for (int i = 0; i < length; i++) {
            numbers[i] = Integer.parseInt(br.readLine());
        }

        StringBuilder sb = new StringBuilder();
        Node root = new Node(numbers[0], null, null);
        sb.append(count + "\n");
        for(int i=1; i<length; i++){
            root.insert(numbers[i], root);
            sb.append(count + "\n");
        }
        System.out.println(sb.toString());
    }
}