[백준] 2957 이진 탐색 트리 풀이 Java, BST, TreeSet

 

BST(Binary Search Tree, 이진 탐색 트리)

---

이진 탐색 트리는 모든 노드가 많아야 2개의 자식 노드를 가지고 있는 트리이고, 각 노드에는 수가 하나씩 쓰여있다.

만약 어떤 노드에 쓰여 있는 수가 X라면, 그 노드의 왼쪽 서브트리에는 X보다 작은 수, 오른쪽 서브트리에는 X보다 큰 수만 저장되어 있어야 한다.

배열의 첫 번째 수를 루트 노드로 놓고, 다른 나머지 수들을 순서대로 삽입하면서 이진 탐색 트리를 만들려고 한다.

즉, 첫 번째 수를 제외한 모든 수에 대해서 insert(X,root)를 실행하는 것과 같다.

이진 탐색 트리에 삽입하는 함수는 다음과 같다.

 

insert(number X, node N)
    카운터 C값을 1 증가시킨다
    if X가 노드 N에 있는 수보다 작다면
        if N의 왼쪽 자식이 없다면
            X를 포함하는 새 노드를 만든 뒤, N의 왼쪽 자식으로 만든다
        else
            insert(X, N의 왼쪽 자식)
    else (X가 노드 N에 있는 수보다 크다면)
        if N의 오른쪽 자식이 없다면
            X를 포함하는 새 노드를 만든 뒤, N의 오른쪽 자식으로 만들기
        else
            insert(X, N의 오른쪽 자식)

 

Java에서 제공하는 BST 클래스(TreeSet)

---

TreeSet은 BST 구조로 이루어져 있으며 BST 중에서도 성능이 좋은 Red-Black Tree로 구현되어 있다.

 

 

* Red-Black Tree

일반적인 이진 탐색 트리는 트리의 높이만큼 시간이 걸리는데 한 쪽으로 치우칠 수 있는 데이터가 들어오면 굉장히 비효율적이 된다.

이 문제를 보완하기 위해 레드-블랙 트리를 사용한다.

 

레드 블랙 트리의 특성

• 빨간색 노드의 자식은 검정색이며 빨간 노드가 연속으로 나올 수 없다.
• 모든 리프 노드에서 Black Height는 같다. 즉, 리프노드에서 루트노드까지 갈 때 검정색 노드의 갯수가 같다.

위 속성 때문에 노드를 계속해서 재배치한다.

https://coding-factory.tistory.com/555

 

 

TreeSet에 새로운 데이터를 추가 할 때,

이미 값이 tree에 존재한다면 false를 리턴하고 없으면 삽입 후 treu를 리턴한다.

# 값 추가
TreeSet<Integer> tree = new TreeSet<Integer>();
treeSet.add(new Integer(10));
treeSet.add(new Integer(7));

TreeSet<Integer> tree2 = new TreeSet<Integer>(set1); // set1의 원소들을 가짐

# 값 삭제
tree.remove(10);
tree.clear();

# 값 출력
tree.first(); // 최솟값
tree.last(); // 최댓값
tree.higher(7); // 입력값보다 큰 데이터 중 최솟값을 출력하며 없으면 null
tree.lower(7); // 입력값보다 작은 데이터 중 최댓값을 출력하며 없으면 null

# 내림차순 정렬
NavigableSet<Integer> desc = tree.descendingSet();

#오름차순 정렬
NavigableSet<Integer> asc = desc.descendingSet();

#범위 검색
## 100 미만인 점수 검색
NavigableSet<Integer> scope = tree.headSet(100,false);

## 100 이하인 점수 검색
NavigableSet<Integer> scope = tree.tailSet(100,true);

## 50 이상 100 미만의 점수 검색
NavigableSet<Integer> scope = tree.subSet(50,true,100,false);

 

문제

---

2957번: 이진 탐색 트리

 

풀이

문제 설명에서 친절하게 주어지는 Node 삽입 방법에 따라 값을 출력하도록 구현하면 시간초과가 발생한다.

이 문제는 BST의 특징을 이용해야 풀 수 있다. 

우선, 이 문제의 포인트는 삽입된 Node의 높이를 출력하라 이다.

 

특정 Node의 높이는 삽입 전,
height = Max(Node보다 작은 수 중 최댓값의 높이, Node보다 큰 수 중 최솟값의 높이) + 1

TreeSet을 사용하면 아래와 같이 구할 수 있다.

height[val] = Math.max(height[tree.lower(val)], height[tree.higher(val)]) + 1

 

 

왜냐하면 TreeSet의 lower, higher 함수는 아래와 같기 때문이다.

tree.higher(7); // 입력값보다 큰 데이터 중 최솟값을 출력하며 없으면 null
tree.lower(7); // 입력값보다 작은 데이터 중 최댓값을 출력하며 없으면 null

 

포인트 1 : higher과 lower 함수 호출 시 값이 없으면 Null 이 리턴된다.

Null이 리턴되지 않게 범위에서 벗어나는 0,N+1을 미리 넣어놓고 높이는 -1로 만든다.

Tree를 그려보면 0과 N+1은 범위에서 벗어나기 때문에 높이에 아무런 영향을 주지 않는다.

(0은 항상 제일 위에 있고, N+1은 항상 제일 오른쪽 아래에 있다.)

 

포인트 2 : 결과를 담는 변수는 Long 으로 선언해야 한다

이유는 N의 최대는 300,000 이다. 최악의 경우로 1~300,000 까지의 수가 1씩 증가하며 들어온다고 생각하자.

간단하게 생각해서 1에서 300,000까지 수를 더한다고 생각해도 n(n+1)/2 = 300,000(300,001)/2 결과는 int 범위를 넘는다.

따라서 Long으로 선언해야 한다.

 

포인트 3 : BufferedReader가 아닌 Scanner로 입력받으면 메모리 초과가 발생한다.

 

포인트 4 : StringBuilder로 출력(1320ms) vs 그때그때 print(3332ms)

 

---

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

public class Main {
	static int N;

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

		N = Integer.parseInt(br.readLine());
		int[] h = new int[N + 2];

		TreeSet<Integer> tree = new TreeSet<>();
		tree.add(0);
		tree.add(N + 1);

		h[0] = -1;
		h[N + 1] = -1;

		long res = 0;

		for (int i = 0; i < N; i++) {
			int in = Integer.parseInt(br.readLine());

			h[in] = Math.max(h[tree.lower(in)], h[tree.higher(in)]) + 1;
			tree.add(in);

			res += h[in];
			sb.append(res + "\n");
		}
		System.out.println(sb);
	}
}

 

References

https://velog.io/@jeewoo1025/%EB%B0%B1%EC%A4%80-2957%EB%B2%88-%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-%ED%8A%B8%EB%A6%AC

https://coding-factory.tistory.com/555