[백준/BOJ] 백준 2957번 : 이진 탐색 트리

www.acmicpc.net/problem/2957

2957번: 이진 탐색 트리

c에 더해지는 값은 해당 수가 들어가는 트리의 깊이이다. map<int, int> tree에 (번호와, 트리에서 깊이)를 저장하여 upper_bound를 통해 현재 트리의 정보 중 입력받은 수 보다 큰 것 중 가장 작은 것을 찾고, 이를 통해 해당 수가 들어갈 트리의 깊이를 구한다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <map>
using namespace std;

int n;
long long c = 0;
map<int, int> tree; //(번호와,트리에서 깊이)
map<int, int>::iterator it;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int input;
		int small_depth;
		int big_depth;

		cin >> input;

		//트리에 아무것도 없을때
		if (tree.size() == 0)
		{
			tree.insert(make_pair(input, 0));
		}

		else
		{
			it = tree.upper_bound(input); //트리에 정보중 입력받은 수 보다 큰것중 가장 작을것을 찾는다

			if (it == tree.begin()) //트리에 모든 수가 다 클때, 트리의 가장 왼쪽 끝에 들어가야 된다
			{
				big_depth = (*it).second;
				tree.insert(make_pair(input, big_depth + 1));
				c += (long long)(big_depth + 1); //해당 수가 들어가는 깊이
			}

			else if (it == tree.end()) //트리의 모든 수가 입력받은 수 보다 작을때, 트리의 가장 오른쪽 끝에 들어가야 된다
			{
				it--;
				small_depth = (*it).second;
				tree.insert(make_pair(input, small_depth + 1));
				c += (long long)(small_depth + 1); //해당 수가 들어가는 깊이
			}

			else
			{
				int big_depth = (*it).second;
				it--;
				int small_depth = (*it).second;

				tree.insert(make_pair(input, max(small_depth, big_depth) + 1));
				c += (long long)(max(small_depth, big_depth) + 1); //해당 수가 들어가는 깊이
			}
		}

		cout << c << "\n";
	}


	return 0;
}