C++ / 백준 / 1946 / 신입 사원

문제

 

https://www.acmicpc.net/problem/1946

1946번: 신입 사원

문제풀이

 

지원자 A가 합격하려면 나머지 모든 지원자의 성적과 비교했을 때, A의 서류성적 < B의 서류성적, A의 면접성적 < B의 면접성적인 경우가 없으면 된다. 이를 등수로 나타내면 A의 서류 등수 > B의 서류 등수, A의 면접 등수 > B의 면접 등수만 아니면 된다.

 

처음에는 이중 반복문을 이용해서 풀었는데 시간초과가 나서 투 포인터 느낌으로 풀었다.

먼저 가장 중요한 것은 등수의 정렬이다.

sort 함수를 이용하여 오름차순으로 등수를 정렬한다.

 

그다음 left와 right 변수를 이용해 left에는 기준 지원자, right는 심사할 지원자로 둔다.

서류등수를 기준으로 오름차순을 했기 때문에 반복문을 돌면서 서류등수는 무조건 증가하므로, 면접 등수만 비교하면 된다.

left에는 면접등수가 높은 지원자의 번호를, right에는 항상 +1씩 하여 다음 지원자로 넘어가면 된다.

 

코드

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

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

	int T(0);
	cin >> T;

	for (int test_case = 1; test_case <= T; ++test_case) {
		int N(0);
		cin >> N;
		vector<pii>grade(N);
		for (int idx = 0; idx < N; ++idx) {
			cin >> grade[idx].first >> grade[idx].second;
		}
		sort(grade.begin(), grade.end());

		int left(0), right(1), answer(N);
		while (right < N) {
			if (grade[left].second < grade[right].second) {
				--answer;
			}
			else if (grade[left].second > grade[right].second) {
				left = right;
			}
			++right;
		}

		cout << answer << '\n';
	}
}