[백준 2957] 이진 탐색 트리 (자바)

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

2957번: 이진 탐색 트리

 

 

난이도 : 플레 5

 

문제에서 보여준 수도 코드로 트리를 구현하여 정직하게 풀면 시간 초과가 납니다.

최대 30만 개의 입력이 들어옵니다. 1~30만까지 차례대로 입력이 주어졌을 때 정석 풀이대로 한다면 O(N^2)의 시간 복잡도이기 때문에 시간 초과가 납니다.

저는 TreeSet을 이용하여 풀었습니다. 제가 생각한 풀이가 너무 복잡해 다른 풀이를 보며 공부하다가 TreeSet의 lower와 higher 메소드를 알게 되었고, 이 메소드들을 이용해 풀었습니다.

 

Set에서는 가장 가까운 원소를 집고, 배열에서는 count 값을 관리합니다.

숫자 n이 트리에 위치할 공간은 

1. n보다 작은 수의 오른쪽
2. n보다 큰 수의 왼쪽

이렇게 2가지 입니다.

즉 트리에서 n보다 작은 수와 큰 수의 위치를 확인 후 그 수의 밑에 위치시키면 됩니다. 깊이는 1 깊어집니다.

트리에 6과 8이 있고, 7을 넣는다 했을 때 7은 8의 아래로 가야 합니다.(6에는 이미 8이 연결돼 있으니) 즉, 작은 수와 큰 수 중 깊이가 더 깊은 수를 선택해 그 밑에 위치시켜줍니다.

경곗값 설정을 위해 0과 n+1을 세팅해줍니다.

 

예제인 8, 3, 5, 1, 6, 8, 7, 2, 4를 이용하여 예를 들어보겠습니다.

 

3 추가

5 추가

1, 6 추가

8 추가

모든 입력 완료

 

이처럼 배열과 set이 채워지게 됩니다.

적절히 카운트를 출력해줍니다.

---

메소드

void main

입력을 받고 Set, 배열을 위에서 설명한 대로 세팅해줍니다.

입력받은 수 보다 크고 작은 수를 찾고 그중 더 큰 값보다 +1 하여 배열에 넣어줍니다.

이것이 깊이가 됩니다.