[BOJ] 백준 [2957] 이진탐색트리 JAVA

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

2957번: 이진 탐색 트리

[문제]

[풀이]

평범한 이진트리 만드는 문제이다.
하지만 시간제한과 메모리에 비해 주어지는 N을 보니 곱해 통과하지 않을듯 하다 .. 결국 시간초과

왜 ..? 보통 노드의 수를 N이라고하면 탐색하는데 걸리는시간은 O(logN)이다.
하지만 만약 연속된 수만 나와서 편향된 트리가 만들어진다면 .. ? => O(N)

편향된 트리가 되지 않게하기 위한 균형잡힌 트리가 있다. => Red-black 트리.
이 트리는 삽입하려는 노드의 삼촌노드( 부모의 부모의 자식) 를 보고 편향되지 않게 균형을 맞춰주기때문.

그런데 우리가 흔히 쓰는 컬렉션도 위와같은 균형트리구조를 쓰는 컬렉션이있다.
TreeSet 이나 HashMap같이 .. 

이중 TreeSet의 컬렉션을 이용해서 간단하게 해보자.
TreeSet 의 내부메소드 중에 lower , higher 가 있는데 , 이 메서드는 파라미터로 특정 값을 기준으로 받고
이 기준에서 봤을때 제일 가까운(자식or부모) 값을 return 해준다. 이게 무슨 말이냐면
key를 기준으로 해서 제일 가까운 수를 반환 해준다는 것. 가령 1~10 까지 트리에 저장되있다고 가정하고
key가 5인 이진트리의 왼쪽자식은 4, 오른쪽자식은 7 이라고 했을 때 
lower(5) 로 던져주면 4를 , higher(5)를 던져주면 7을 리턴해준다는 뜻.

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

 

 
import java.util.*;
import java.io.*;
import java.util.stream.Collectors;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long ans=0;
        int[] depth = new int[n+2];
        depth[0]=-1; depth[n+1]=-1;
        TreeSet<Integer> tree = new TreeSet<>();
        tree.add(0);tree.add(n+1);
        for(int i=0;i<n;i++){
            Integer e = Integer.parseInt(br.readLine());
            depth[e] = Math.max(depth[tree.lower(e)],depth[tree.higher(e)])+1;
            tree.add(e);
            ans+=depth[e];
            System.out.println(ans);
        }
    }
}