[백준 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 하여 배열에 넣어줍니다.

이것이 깊이가 됩니다.

 

	import java.io.BufferedReader;
	import java.io.InputStreamReader;
	import java.util.TreeSet;
	public class p2957 {
	public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int n = Integer.parseInt(br.readLine());
	TreeSet<Integer> set = new TreeSet<>();
	StringBuilder sb = new StringBuilder();
	long count = 0;
	int depth[] = new int[n+2];
	depth[0] = -1;
	depth[n+1] = -1;
	set.add(0);
	set.add(n+1);
	for(int i = 0; i < n; i++) {
	int number = Integer.parseInt(br.readLine());
	depth[number] = Math.max(depth[set.lower(number)], depth[set.higher(number)]) + 1;
	set.add(number);
	count += depth[number];
	sb.append(count + "\n");
	}
	System.out.println(sb.toString());
	}
	}

view raw p2957.java hosted with ❤ by GitHub