BOJ 백준 2957 : 이진 탐색 트리

시작하면서

　이번 문제는 맵(Map) 문제이다. 이진 탐색 트리 문제를 찾다가 좀 더 심화된 Red-Black Tree를 사용하는 문제를 푼다.

BOJ 2957 - 이진 탐색 트리

​

문제 이해

문제를 읽어보자. 먼저 이 문제에서 나오는 변수는 총 4가지이다.

• N : 수열의 크기
• value : 수열의 수가 차례로 입력

​

문제 아이디어

　N의 최대값은 30만이다. 문제를 보면 이진 탐색 트리에 삽입하는 함수의 로직이 나와있다. 하지만 이대로 문제를 풀면 시간초과가 발생하게 된다. 시간 초과가 발생하는 경우는 한쪽에 치우친 이진 탐색 트리가 만들어진 경우이다(시간 복잡도 O(n^2)).

​ 그래서 생각을 바꾸어서 이진 탐색 트리에 그대로 넣지 않고, 이진 트리를 균등하게 유지해주는 Red-Black Tree에 valkue와 count를 넣는다. 방법은 다음과 같다.

1. map(Red-Black Tree)에서 value 가장 가까운 값들을 찾는다.
   • 가장 가까운 값 [1] : value 보다 큰 값 중에 가장 작은 값
   • 가장 가까운 값 [2] : value 보다 작은 값 중에 가장 큰 값
2. 가장 가까운 값들의 count를 비교해서 더 큰 count를 가진 값을 선정한다.
   • 더 큰 count 쪽이 최근에 들어간 값이고, 이 값 다음에 value가 들어가야 하므로 더 큰 count를 찾는 것
3. map(Red-Black Tree)에 값과 count를 함께 넣는다.
4. 이전 count에 현재 count를 더해서 따로 저장한다.
5. 저장한 count를 출력한다.

​

해결

#include <iostream>
#include <vector>
#include <map>

using namespace std;

void InsertNode(map<int, long long int>& tree, vector<long long int>& countVector, int value);

int main()
{
	map<int, long long int> tree;
	vector<long long int> countVector;
	int N, value;

	// sync off
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	// ----------

	// 제일 앞과 뒤에 '-1' count를 넣어서 upper/lower를 찾을 때 null 접근이 되지 않도록 방지
	tree.insert(make_pair(0, -1));
	tree.insert(make_pair(300001, -1));

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> value;

		InsertNode(tree, countVector, value);
	}

	for (int i = 0; i < countVector.size(); i++)
	{
		cout << countVector[i] << "\n";
	}

	return 0;
}

void InsertNode(map<int, long long int>& tree, vector<long long int>& countVector, int value)
{
	// 기준 원소보다 큰 첫 번째 iterator
	map<int, long long int>::iterator upperIter;

	// 기준 원소보다 작은 첫 번째 iterator
	map<int, long long int>::iterator lowerIter;

	long long int count = 0;

	if (countVector.empty() == true)
	{
		countVector.push_back(count);
	}
	else
	{
		upperIter = tree.upper_bound(value);
		lowerIter = upperIter; lowerIter--;

		count = (upperIter->second > lowerIter->second) ? upperIter->second : lowerIter->second;
		count++;
		
		countVector.push_back(count + countVector[countVector.size() - 1]);
	}

	tree.insert(make_pair(value, count));
}

​

마치며

　upper_bound / lower_bound에 대한 개념과 기능을 돌아볼 수 있는 문제였다. 또한, Red-Black Tree를 잠깐 다시 봤는데 역시나 아직 어렵다. 추후에 카테고리가 나오면 제대로 공부해봐야하는 부분이므로 잘 기억해두자.