algospot 너드인가, 너드가 아닌가? 2 (문제 ID: NERD2) c++

알고스팟 문제 링크: https://algospot.com/judge/problem/read/NERD2

algospot.com :: NERD2

p와 q가 다음과 같이 정의된다.

p: 알고스팟 온라인 채점 시스템에서 푼 문제의 수

q: 밤 새면서 지금까지 끓여먹은 라면 그릇 수

대회에 참가하려는 신청자 a의 문제 수 pa와 그릇 수 qa를 다른 참가 신청자 b의 문제 수 pb와 그릇 수 qb에 비교한다.

이때, pa < pb && qa < qb 이면 신청자 a는 대회에 참가할 수 없다.

한 사람의 참가 가능 여부는 다른 사람들의 문제와 라면 그릇 수에 의해 결정 되기 때문에,

대회에 참가할 수 있는 사람의 수는 새로운 사람이 참가 신청을 할 때마다 계속 바뀐다.

 

신청자들 각각의 p와 q를 x, y로 바꿔서 이차원 평면의 점들로 생각해보자.

대회에 참가하기 위해서는 기존의 점들보다 x값이 크거나 y값이 크거나 둘중 하나는 해야된다.

이는 곧 신청자의 (p,q)에서 p에 바로 오른쪽 점의 y좌표가 q보다 작아야 한다.

위 기준에 맞아서 새 신청자를 참가시킬시에는 새점 (p,q)에서 p에 왼쪽에 있는점의 y좌표가 q보다 작다면 더 이상 대회에 참가할 수 없다.

 

	#include<iostream>
	#include<map>
	using namespace std;
	// <x, y>를 점으로 추상화
	map<int, int> coords;
	// 새로운 점 (x,y)가 기존의 다른 점들에 지배당하는지 확인
	bool isDominated(int x, int y) {
	// x보다 오른쪽에 있는 점중에 가장 왼쪽에 있는점
	map<int, int>::iterator it = coords.lower_bound(x);
	// 없으면 지배당하지 않는다
	if (it == coords.end())return false;
	// 이 점은 x보다 오른쪽에 있는 점들 중 가장 왼쪽에 -> 가장 위에 있는 점
	// 이 점 보다 밑에 있으면 이점보다 x값도 작고 y값도 작은게 됨 -> 너드 아님
	return y < it->second;
	}
	// 새로운 점 (x, y)에 지배당하는 점들을 map에서 지움
	void removeDominated(int x, int y) {
	map<int, int>::iterator it = coords.lower_bound(x);
	// x보다 왼쪽에 있는 점이 없는 경우
	if (it == coords.begin())return;
	--it;
	while (true) {
	// it가 가르키는 점보다 y가 작으면 더 이상 지울게 없음
	if (it->second > y)break;
	// it다음 점이 없으므로 it가 가르키는 점만 지우고 종료
	if (it == coords.begin()) {
	coords.erase(it);
	break;
	}
	// it를 지우고 다음 왼쪽 점을 가르킨다.
	else {
	map<int, int>::iterator jt = it;
	jt--;
	coords.erase(it);
	it = jt;
	}
	}
	}
	// (x,y)가 추가되었을 때 coords를 갱신하고 남아있는 점의 갯수 반환
	int registered(int x, int y) {
	// 새 점이 지배당하면 그냥 새 점을 버리고 끝
	if (isDominated(x, y))return coords.size();
	// 새 점에 의해 지워지는 점들을 제거하고 coords갱신
	removeDominated(x, y);
	coords[x] = y;
	return coords.size();
	}
	int main() {
	int testcase;
	cin >> testcase;
	while (testcase--) {
	coords.clear();
	int n, x, y, sum = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
	cin >> x >> y;
	sum += registered(x, y);
	}
	cout << sum << endl;
	}
	}

view raw algospot 너드인가, 너드가 아닌가? 2 (문제 ID: NERD2).cpp hosted with ❤ by GitHub

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/22.%20BinarySearchTree/NERD2.cpp

GitHub - sbl133/JongmanBook

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2