백준 2957번 이진 탐색 트리

문제 링크입니다: https://www.acmicpc.net/problem/2957

2957번: 이진 탐색 트리

N은 최대 300,000이고 이진 탐색 트리를 구성할 때 최악의 경우 skewed binary tree가 되기 때문에 시간복잡도가 O(N^2)이 될 수가 있습니다.

따라서, upper_bound를 이용해 풀어야하는 문제였습니다.

 

처음 들어오는 숫자는 무조건 root가 되고,

이후에 들어오는 숫자는 upper_bound를 이용해 아래와 같은 두 조건을 검사해야합니다.

i) 트리 내 제일 큰 숫자가 아닐 경우

ii) 트리 내 제일 작은 숫자가 아닐 경우

 

검사한 두 조건에서 구한 높이 중 더 높은 값을 C에 더하고 해당 숫자는 그 높이에 있는 노드의 자식노드이기 때문에 map에 저장할 때는 (해당 높이 + 1)을 저장해줘야합니다.

 

* kks227님 풀이를 참고해서 풀었습니다. 항상 감사합니다.

 

	#include <iostream>
	#include <algorithm>
	#include <map>
	using namespace std;
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int N;
	cin >> N;
	long long C = 0;
	map<int, int> depth;
	for (int i = 0; i < N; i++)
	{
	int num;
	cin >> num;
	if (i == 0)
	{
	depth[num] = 1; //root
	cout << C << "\n";
	continue;
	}
	auto iterator = depth.upper_bound(num);
	int height = 0;
	// 제일 큰 숫자가 아닌 경우
	if (iterator != depth.end())
	{
	height = iterator->second;
	}
	// 제일 작은 숫자가 아닌 경우
	if (iterator != depth.begin())
	{
	iterator--;
	height = max(height, iterator->second);
	}
	C += height;
	cout << C << "\n";
	// 자식 노드이므로 + 1
	depth[num] = height + 1;
	}
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~