백준 1946 - 신입 사원

문제 설명

언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다.

그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.

이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면 점수가 두 개씩 주어지면 두 점수가 다른 사람에 비해 모두 낮으면 뽑지 않는 것이다.

 

간단하게 생각해 보면 첫 번째 등수를 기준으로 정렬을 진행한 뒤 이전 등수에 비해 두 번째 등수가 낮으면 된다.

예를 들어 보자.

1 4
2 3
3 2
4 1
5 5

이런 경우 1~5로 첫 번째 등수는 정렬되어 있다.

이때 두 번째 등수 (2, 3)은 이전 등수 (1, 4) 보다 서류 등수가 낮은 것은 분명하다.

하지만 확인되지 않은 것은 면접 등수이다.

즉, 면접 등수 3이 4보다 작기 때문에 두 번째 등수(2, 3)는 선발될 수 있는 것이다.

따라서 위에서부터 순회하며 이전 등수보다 면접 등수가 작은게 있다면 해당 인원은 선발되지 않는 것이다.

하지만, 이렇게 모두 훑어가면 시간 초과가 발생한다.

 

이를 해결하기 위해서는 우선 순위 큐를 사용하면 된다.

이전 등수의 면접 점수를 모두 저장해놓으면서 가장 작은 것을 뽑아냈을 때 자신의 면접점수보다 크다면 선발될 수 있는 것이다.

우선순위 큐는 가장 큰 수를 뽑아내는 게 기본이다.

정렬 기준을 함수로 전달할 수 있지만, 간단하게 -를 붙여 순서를 뒤바꾸면 된다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9

using namespace std;
int T, N;
vector<pair<int, int>> people;

int main() 
{
    INPUT_OPTIMIZE;
    
	cin >> T;

	while (T--)
	{
		cin >> N;

		people.clear();

		for (int i = 0; i < N; i++)
		{
			int a, b;
			cin >> a >> b;

			people.push_back({ a,b });
		}

		sort(people.begin(), people.end());

		int cnt = 0;
		priority_queue<int> pq;

		for (int i = 0; i < N; i++)
		{
			auto [a, b] = people[i];
			
			if (pq.empty())
			{
				cnt++;
			}
			else
			{
				auto top = pq.top();
				top *= -1;
				if (top > b)
				{
					cnt++;
				}
			}

			pq.push(-b);
		}

		cout << cnt << "\n";
	}

	return 0;
}

---