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

문제

대 성황이었던 지난 알고스팟 연간 모의고사 이후 프로그래밍 대회의 열기는 날로 뜨거워져 올해는 10만명이 넘는 사람들이 참가 신청을 할 것으로 예상되고 있습니다. 그러나 채점관을 할 자원 봉사자는 예년과 똑같이 5명뿐이라, 이 사람들을 대회에 다 참가시킬 수는 없습니다. 따라서 올해에도 참가 신청을 한 사람 중 진정한 프로그래밍 너드들만을 대회에 참가할 수 있도록 받아 주기로 했습니다.


종만의 새로운 이론에 따르면, 어떤 사람의 너드 지수는 다음 두 가지 값에 의해 결정됩니다.

• 알고스팟 온라인 채점 시스템에서 푼 문제의 수 p
• 밤 새면서 지금까지 끓여먹은 라면 그릇 수 q
  
  
  이 이론에 따르면 어떤 참가 신청자 a 의 문제 수 pa 와 그릇 수 qa 를 다른 참가 신청자 b 의 문제 수 pb 와 그릇 수 qb 에 각각 비교했을 때, pa < pb, qa < qb 라면 참가 신청자 a 는 너드일 가능성이 없습니다. 조직위는 너드일 가능성이 있는 사람들만을 대회에 받아주기로 했습니다.
  한 사람의 참가 가능 여부는 다른 사람들에 의해 결정되기 때문에, 대회에 참가할 수 있는 사람의 수는 새로운 사람이 참가 신청을 할 때마다 계속 바뀝니다. 예를 들어 다음과 같은 4명의 사람들이 순서대로 참가 신청을 했다고 합시다.

참가자	종만	재훈	효승	광규
문제 수	72	57	74	64
라면 그릇 수	50	67	55	60

종만과 재훈이 순서대로 대회 참가 신청을 하면 대회에 참가할 수 있는 사람의 수는 각각 1, 2 로 늘어나지만, 효승이는 문제 수도 라면 그릇 수도 종만보다 많으므로 효승이 참가 신청을 한 시점에서 종만은 더 이상 대회에 참가할 수 없습니다. 따라서 이 네 명이 참가 신청을 할 때마다 참가 가능자의 수는 1, 2, 2, 3으로 변합니다.
이렇게 각 사람이 참가 신청을 할 때마다 대회에 참가할 수 있는 사람들의 수가 어떻게 변하는지 계산하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 참가 신청한 사람들의 수 N (1 <= N <= 50000) 이 주어집니다. 그 후 N 줄에 각 2개의 정수로 각 사람의 문제 수 pi 와 라면 그릇 수 qi 가 참가 신청한 순서대로 주어집니다 (0 <= pi,qi <= 100000) . 두 사람의 문제 수나 라면 그릇 수가 같은 경우는 없다고 가정해도 좋습니다.
입력의 양이 많으므로 가능한 빠른 입력 함수를 사용하는 것이 좋습니다.

출력

각 사람이 참가 신청을 할 때마다 대회 참가 자격이 되는 사람의 수를 계산한 뒤, 각 테스트 케이스마다 그 합을 출력합니다.

예제 입력

2
4
72 50
57 67
74 55
64 60
5
1 5
2 4
3 3
4 2
5 1

예제 출력

8
15

First Thoughts

c++ STL library map 사용

c++에는 이진 트리를 구현하는 라이브러리가 이미 있을거라는 걸 예상하고 여러 라이브러리를 찾아봤다. 그 중 찾은게 set과 map인데 처음 pair을 이용하여 set 구조를 이용하려고 했으나 자료와 원소처럼 한 쌍으로 이루어진 경우는 주로 map을 사용한다는 것을 알게되었다. 그래서 map을 사용하여 key값으로는 문제수를, value값으로는 라면 그릇 수를 저장하였다. 새로운 입력을 input하는 과정에서 라면의 수와 문제의 수가 적은 학생이 발견되면 해당 노드를 삭제하는 방식으로 코드를 작성하였다.

My Code

#include <iostream>
#include <set>
#include <map>
#pragma warning(disable:4996)
using namespace std;
map<int, int>m;
int in_possible(int p, int q) {
	if (m.empty()) {
		m.insert(pair<int, int>(p, q));
		return 1;
	}
	map<int, int>::iterator iter;
	for (iter = m.begin(); iter != m.end(); ) {
		if ((*iter).first < p && (*iter).second < q) {
			m.erase(iter++);
		}
		else {
			++iter;
		}
	}
	m.insert(pair<int, int>(p, q));
	return m.size();
}
int main(void) {
	int C;
	int i,j;
	int N;
	int p, q;
	int total = 0;
	cin >> C;
	for (i = 0; i < C; i++) {
		scanf("%d", &N);
		total = 0;
		for (j = 0; j < N; j++) {
			scanf("%d %d", &p, &q);
			total+=in_possible(p, q);
		}
		printf("%d\n",total);
		m.clear();
	}	
}

Answer Code

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
map<int, int> coords;

//지배 당하는지 여부
bool isDominated(int x, int y) {
	map<int, int>::iterator it = coords.lower_bound(x);//x이상의 키 중 가장 작은 값
	//그런 점이 없으면 지배당하지 않는다
	if (it == coords.end())
		return false;
	return y < it->second;
}
void removeDominated(int x, int y) {
	map<int, int>::iterator it = coords.lower_bound(x);
	if (it == coords.begin())
		return;
	--it;
	while (true) {
		if (it->second > y)
			break;
		if (it == coords.begin()) {
			coords.erase(it);
			break;
		}
		else {
			map<int, int>::iterator jt = it;
			--jt;
			coords.erase(it);
			it = jt;
		}
	}
}
int registered(int x, int y) {
	if (isDominated(x, y))
		return coords.size();
	removeDominated(x, y);
	coords[x] = y;
	return coords.size();
}
int main(void) {
	int C;
	int i,j;
	int N;
	int p, q;
	int sum = 0;
	cin >> C;
	for (i = 0; i < C; i++) {
		cin >> N;
		sum = 0;
		for (j = 0; j < N; j++) {
			cin >> p >> q;
			sum+=registered(p, q);
		}
		cout << sum << endl;
		coords.clear();
	}
}

Difference & Faults

시간 초과

내가 작성한 코드는 입력을 할 때마다 반복문을 돌아서 시간초과가 뜬다. 해제코드로 효율적이고 빠른 코드 작성법을 보자.

2차원 평면의 이용

해제 코드는 사람의 문제 수와 그릇 수를 좌표 평면에서 x,y좌표로 표현하여 각 좌표들의 위치를 비교하였다. 각 노드를 좌표로 표현하면 x좌표가 증가하는 순서대로 정렬하면 y좌표가 감소된다는 것을 알 수 있다. 이는 한 좌표가 다른 좌표의 내부에 있는지 외부에 있는지 그 상대적 위치를 파악하기 쉽게 된다. 또한 map에서 어떤 수 이상의 범위에서 가장 작은 값을 구해주는 lower_bound함수를 이용하여 포함여부를 확인한다.

Impressions

이진검색 트리

다른 언어는 잘 모르겠지만 c++은 정말 다양한 라이브러리를 내포하고있다. 그래서 그 라이브러리를 잘 활용할 줄만 알면 구현은 복잡하지 않은 거 같다. 하지만 라이브러리와 라이브러리 내 함수의 정확한 사용법을 알고 효율적으로 잘 사용해야함을 느꼈다.

key와value

앞에 "Difference & Faults"에서도 거론한 가장 큰 차이점이 나에게는 가장 큰 배움이었다. key와 value를 단순히 이진 트리에 저장한다고 생각하지만 이를 2차원 평면으로 생각하면 그 상대적인 위치를 쉽게 알 것이다. 때로는 한 자료구조를 그 자체로 볼 것이 아니라 조금 더 유연하게 볼 줄도 알아야한다.

Summary

문제 자체는 이해하기 어렵거나 아이디어 구현이 어렵진 않았다. 하지만 해제 코드를 보니 조금 더 나아가서 생각했더라면 좋았을 거 같다. 또한 c++에는 다양한 라이브러리들이 있어서 좋지만 많은 라이브러리들의 사용을 정확히 알고 사용할 필요가 있다.