[BOJ] 1946 : 신입 사원 - travelbeeee

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

---

[ 알고리즘풀이 ]

 서류심사 성적과 면접시험 성적 2가지가 있을 때, 하나를 기준으로 Sorting을 한다면 나머지 하나는 O(N) 만에 Check를 할 수 있습니다. 따라서, O(NlogN + N) 으로 문제를 해결할 수 있습니다.

 테스트케이스 2번을 가지고 설명해보겠습니다.

Sorting 전	서류심사 성적	면접시험 성적
1번 사람	3	6
2번 사람	7	3
3번 사람	4	2
4번 사람	1	4
5번 사람	5	7
6번 사람	2	5
7번 사람	6	1

 이런 상황에서 서류 심사 성적을 기준으로 Sorting을 진행해보겠습니다.

Sorting 후	서류심사 성적	면접시험 성적
4번 사람	1	4
6번 사람	2	5
1번 사람	3	6
3번 사람	4	2
5번 사람	5	7
7번 사람	6	1
2번 사람	7	3

 이제 서류심사 성적을 기준으로는 Sorting이 끝났습니다. 따라서, 면접시험 성적만 앞에서부터 순회해보겠습니다. 당연히 4번 사람은 서류심사 성적이 모든 사람보다 좋으므로(Sorting 결과에 의해) 무조건 뽑히는 사람이 됩니다. 현재까지 면접시험 최대 성적은 4등이므로 따로 저장해둡니다. 6번 사람은 4번 사람보다 서류심사 성적이 낮기 때문에 4번 사람보다 면접 시험 성적만 좋으면 됩니다. 하지만, 현재 면접시험 최대 성적이 4등이므로 6번 사람은 탈락하게 됩니다. 1번 사람도 면접 시험 성적이 현재 최대 성적 4등보다 좋지 않으므로 조건에 미달합니다. 3번 사람은 현재 면접 최대 면접 시험 성적 4등보다 면접 시험 성적이 좋으므로 뽑히고, 최대 면접 시험 성적을 2등으로 갱신합니다. 이 과정을 반복하면 정답을 얻을 수 있습니다.

 

 정리하면, Sorting 후 면접시험 성적을 순회하며 현재까지 나온 제일 좋은 면접시험 성적보다 좋은 면접시험 성적이 나온다면 그 사람은 현재까지 순회한 사람들보다는 면접 시험 성적이 좋고, 아직 순회하지 않은 사람들보다는 서류심사 성적이 좋은 것을 알 수 있습니다. 

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int T;
	cin >> T;
	while (T--) {
		int N, a, b;
		cin >> N;
		vector<pair<int, int>> V;
		for (int i = 0; i < N; i++){
			cin >> a >> b;
			V.push_back(make_pair(a, b));
		}
		sort(V.begin(), V.end());
		int count = 1, minimum = V[0].second;
		for(int i = 1; i < N; i++)
			if (V[i].second < minimum) {
				minimum = V[i].second;
				count++;
			}
		cout << count << '\n';
	}
}

---