알고스팟: 너드인가, 너드가 아닌가? 2 (ID: NERD2)

[문제 링크]

algospot.com :: NERD2

---

알고리즘 문제해결 전략의 이진검색 트리를 공부하면서 풀게된 문제였다.

예전에 풀었던 백준: 신입사원 문제 와 거의 같은 유형의 문제라고 생각한다.

---

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

bool isDominated(map<int, int>& data, int p, int q)
{
	map<int, int>::iterator iter = data.lower_bound(p);

	if (iter == data.end()) return false;

	return iter->second > q;
}

void removeDominated(map<int, int>& data, int p, int q)
{
	map<int, int>::iterator iter = data.lower_bound(p);

	if (iter == data.begin()) return;
	iter--;

	while (1)
	{
		if (iter->second > q) return;

		if (iter == data.begin())
		{
			data.erase(iter); 
			break;
		}
		else
		{
			map<int, int>::iterator temp = iter;
			temp--;
			data.erase(iter);
			iter = temp;
		}
	}
}

int main(void)
{
	cin.tie(0);
	ios_base::sync_with_stdio(0);

	int tc;
	cin >> tc;

	while (tc--)
	{
		int N;
		cin >> N;

		int cnt = 0;
		map<int, int> coords;

		for (int i = 0; i < N; i++)
		{
			int p, q;
			cin >> p >> q;

			if (isDominated(coords, p, q))
				cnt += coords.size();
			else
			{
				removeDominated(coords, p, q);
				coords[p] = q;
				cnt += coords.size();
			}
		}

		cout << cnt << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 142 day