[백준]이진탐색트리

백준저지

[이진탐색트리]https://www.acmicpc.net/problem/2957

• 필자에 너무 어려웠던 문제이다. 이 문제를 풀기위해 3주를 고민했다.

• 어렵게 풀었던 만큼 이진탐색트리의 삽입, 삭제, 탐색은 확실하게 이해도가 많이 올라간 것 같아 기분이 좋다.

• 추가적으로 Map이란 STL사용법도 확실히 많이 익숙해진 듯하다.

 

[풀이]

• 기본적으로 이진탐색트리의 삽입의 성질과 위 문제의 의도를 정확하게 이해해야 풀 수 있는 문제이다.

→ root의 값보다 크면 오른쪽, root의 값보다 작으면 왼쪽

• 아마 처음 접근은 위 문제에서 수도코드로 짜여있는 예시대로 구현을 했을 것이다.

• 필자도 저 예시대로 재귀로 구현해도 해보고 반복으로 구현도 해보고 배열을 30만개 만들어서도 해보고...

• 결론은 이진탐색트리를 구현하는 방식으로 코딩을 했는데 전부 시간초과가 발생했다.

• 그 이유는 최악의 경우를 생각해보았을 때 30만개가 1부터 30만까지 차례대로 들어온다고 하면 O(N2)의 시간이 나온다. 1초안에 해결할 수 없는 시간이다.

→ 1, 2, 3, 4의 숫자가 차례대로 들어온다고 생각하면,

→ 1일 때 0번 비교

→ 2일 때 1번 비교(1과 비교 후 1의 오른쪽에 삽입)

→ 3일 때 2번 비교(1과 비교, 2와 비교 후 2의 오른쪽에 삽입)

→ 4일 때 3번 비교(1과 비교, 2와 비교, 3과 비교 후 3의 오른쪽에 삽입)

→ 즉, 1부터 30만까지 차례로 입력이 들어왔을 때 비교 횟수는

→ 0+1+2+3+ ⋯ + 299,999 = O(N2)이다.

• 이렇다는 것은 절대 일반적인 이진탐색트리의 방식으로 위 문제를 시간 내에 풀 수 없다는 것을 뜻한다.

• 즉 생각을 전환해야할 필요가 생긴다는 것인데, 문제는 C의 값만을 출력하길 원하고 있다.

• C의 값은 이진트리에 삽입이 될 때 누적된 높이의 값을 뜻한다.

• 필자는 이진트리를 만드는 일련의 과정을 탈피하고 이진트리가 갖고 있는 성질과 문제가 원하는 결과 값(바로 C의 값)에 초점을 맞추어서 문제를 접근하기 시작했다.

 

• 그 결과 하나의 규칙을 발견할 수 있었는데 바로 어떠한 값 X는 “X보다 작은 값들 중 가장 큰 값의 오른쪽에 삽입이 되는 것”과 “X보다 큰 값들 중 가장 작은 값의 왼쪽에 삽입되는 것”이란 성질이 있다는 것을 발견했다.

• 사실 위 문제를 풀기위해 입력된 X가 어떤 트리의 오른쪽 서브트리인지 왼쪽 서브트리인지 알 필요조차 없다. 그냥 입력된 값과 높이를 저장하는 자료구조를 사용하고, “입력한 값 X보다 작은 값들 중 가장 큰 값의 높이”와 “입력한 값 X보다 큰 값들 중 가장 작은 값의 높이”를 구해서 비교한 뒤 더 큰 높이에 1을 추가해서 자료구조에 삽입하면 끝이다.

 

• 왜 위와 같은 원리가 적용이 되는 것일까?

• 바로 이진트리의 성질 중에 있다. 트리에 3과 5가 삽입되어 있다고 하자. 이 상태에서 4가 입력이 되었다고 하자. 4는 어디에 삽입이 될까? 그렇다. 3의 오른쪽 혹은 5의 왼쪽에 삽입이 된다. 그럼 여기서 더 나가보자.

• 만약 3이 먼저 삽입되고 5가 삽입되었다고 하자. 그럼 4는 어디에 삽입이 될까? 맞다. 5의 왼쪽에 삽입된다.

• 그럼 반대로 5가 먼저 삽입되고 3이 삽입되었다고 하자. 그럼 4는 어디에 삽입될까? 그렇다. 3의 오른쪽에 삽입이 된다.

• 슬슬 눈치를 챘을 것이라고 믿어 의심치 않는다.

• 바로 4가 3의 오른쪽에 삽입 되는가 혹은 5의 왼쪽에 삽입되는 가를 결정하는 것은 누가 먼저 삽입되었는가에 달려있고 또 다른 말로 하게 되면 어느 것의 높이가 더 높은가라고 말할 수 있다.

• 다른 숫자로도 연습장에 그려보길 바란다. 필자가 생각한 원리가 그대로 적용될 것이라 생각한다.

• 즉 위 내용을 일반화해보면 아래와 같다.

• “입력된 X의 값보다 작은 것들 중 가장 큰 것의 높이”와 “입력된 X의 값보다 큰 것들 중 가장 작은 것의 높이”를 비교한 후 높이가 큰 것에 +1을 한 것이 입력된 X의 높이가 된다.

 

• 자 푸는 방식은 알았다. 그렇다면 구현을 해보자.

• 사실 구현하는 것도 만만치 않다. “입력된 X보다 작은 값들 중 가장 큰 것”과 “입력된 X보다 큰 값들 중 가장 작은 것”을 구하는 것이 솔직히 간단한 작업은 아니라고 생각한다.(적어도 필자 입장에서는...)

• 그래서 필자는 균형 잡힌 이진트리와 스레드 이진트리를 이용해서 문제를 풀어볼까 생각했는데

• C++의 STL에 분명 입력하면 정렬된 상태로 저장되고,

• 입력된 값의 바로 앞의 값과 바로 뒤의 반복자를 return해주는 STL이 있을 것이라 생각했고 구글링에 들어갔다.

• 바로 map이라는 것이 필자가 찾는 STL이었다!

 

[구현]

• map STL의 설명을 보면 자세히 알 수 있겠지만 간략하게 필자가 이용한 함수를 설명하겠다.

• lower_bound(key)란 함수는 매개변수 key요소를 가지고 있다면 해당 위치의 반복자를 반환한다.

→ key요소의 이전 반복자를 반환하는 것이 없어서 (--m.lower_bound(in))식으로 이전 반복자를 반환하게 하였다.

• upper_bound(key)란 함수는 매개변수 key요소를 가지고 있다면 해당 위치의 다음 위치 반복자를 반환한다.

• lower_bound()와 upper_bound()가 map의 범위에 벗어나는 곳을 접근할 때 Runtime Error가 발생했다.

→ 예를 들어 (1,2) (2,3)을 map에 삽입할 때 upper_bound(2)를 하면 다음 위치 반복자가 없으므로 Runtime Error가 발생했다.

• line14: 그래서 필자는 백준 문제에서 범위가 1<=N<=30만이므로 map에 (0,-1)과 (3000001, -1)을 먼저 삽입한 뒤 Runtime Error의 발생을 막았다.

• line22: lower_bound와 upper_bound를 통해 높이를 구한 뒤 max값에 +1을 하고

• line24: mapArr에 삽입을 하였다.

• 추가적으로 위 문제를 접하면서 cin & cout과 scanf & printf의 입출력 시간 차이가 있다는 것을 깨달았다.

• 아래 코드에서 입출력을 cin & cout으로 바꾸면 시간초과가 나는 현상이 발생했다.

#include <cstdio>
#include <algorithm>
#include <map>

using namespace std;

int main(void) {
	int num;
	long long int C = 0;
	map<int, long long int> mapArr;
	map<int, long long int>::iterator lower_bound;
	map<int, long long int>::iterator upper_bound;

	mapArr.insert(pair<int, long long int>(0, -1));
	mapArr.insert(pair<int, long long int>(300001, -1));
	scanf("%d", &num);

	for (int i = 0; i < num; i++) {
		int in; scanf("%d", &in); long long int dep = 0;
		lower_bound = (--mapArr.lower_bound(in));
		upper_bound = (mapArr.upper_bound(in));
		dep = max(lower_bound->second, upper_bound->second) + 1;
		
		mapArr.insert(pair<int, long long int>(in, dep));
		C += dep;
		printf("%lld\n", C);
	}

	return 0;
}