[C++] 백준/Silver/1946. 신입 사원

문제: 신입 사원(백준 1946번)

문제 분석

이 코드는 신입 사원 선발 문제를 해결하기 위한 코드다.
주어진 t개의 테스트 케이스에 대해 각 지원자의 서류 성적과 면접 성적이 주어진다.
이 중 두 성적 중 하나라도 다른 지원자보다 나은 경우에만 선발한다.
즉, 어떤 지원자가 다른 지원자들에 의해 완전히 밀리지 않는 경우를 찾는 문제다.

알고리즘 설명

1. 입력받기
   각 테스트 케이스마다 n명의 지원자 정보(서류 성적, 면접 성적)를 입력받는다.
2. 정렬
   서류 성적 기준으로 오름차순 정렬한다.
   이로 인해 서류 성적이 앞서는 지원자만 비교하면 된다.
3. 최소 면접 성적 추적
   서류 성적이 낮은 순서로 순회하면서,
   이전까지의 최소 면접 성적(minVal)보다 현재 지원자의 면접 성적이 더 낮다면,
   해당 지원자는 선발 가능하다. 이 경우, answer를 증가시키고 minVal을 갱신한다.
4. 결과 출력
   각 테스트 케이스마다 선발 가능한 지원자의 수를 출력한다.

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t; // 테스트 케이스 개수
    while (t--) {
        int n; cin >> n; // 지원자 수
        vector<pair<int, int>> v(n); // 서류 성적, 면접 성적
        for (int i = 0; i < n; i++) cin >> v[i].first >> v[i].second;

        // 서류 성적 기준 오름차순 정렬
        sort(v.begin(), v.end());

        int minVal = n + 1; // 면접 성적의 최소값
        int answer = 0; // 선발 가능한 지원자 수

        // 선발 여부 판단
        for (int i = 0; i < n; i++) {
            if (v[i].second < minVal) {
                minVal = v[i].second; // 최소 면접 성적 갱신
                answer++; // 선발
            }
        }
        cout << answer << '\n'; // 결과 출력
    }
}