백준 1946번 - 신입 사원

백준 1946번 - 신입 사원

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

문제

• 지원자의 서류심사 성적, 면접 성적의 순위가 주어짐
• 서류심사의 성적이나 면접 성적이 적어도 다른 합격자들 보다 하나는 높아야 하는 경우, 나올 수 있는 최대 합격자의 수

입력

• 테스트 케이스의 개수 T(1 ≤ T ≤ 20)
• 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)
• 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위
• 두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정

출력

• 선발할 수 있는 신입사원의 최대 인원수

접근

• 서류심사의 성적을 오름차순으로 정렬했을 때, 뒤의 지원자의 서류심사 성적은 무조건 앞의 지원자 보다 낮게 된다.

• 이 때, 면접성적까지 앞의 지원자보다 낮게 된다면 합격자가 될 수 없으므로 패쓰!

• 면접성적이 앞의 지원자들보다 좋다면 합격이고, 그 성적이 면접성적의 합격 기준이되며 반복

• 예시)

  7
  3 6
  7 3
  4 2
  1 4
  5 7
  2 5
  6 1
  
  1. 서류심사를 오름차순대로 정렬
  1 4
  2 5
  3 6
  4 2
  5 7
  6 1
  7 3
  
  2. 면접성적을 차례대로 비교
  1 4 <- 다음에 올 사람은 면접성적이 4위보다 좋아야 함 (count : 1)
  2 5 <- Pass
  3 6 <- Pass
  4 2 <- 다음에 올 사람은 면접성적이 2위보다 좋아야 함 (count : 2)
  5 7 <- Pass
  6 1 <- 다음에 올 사람은 면접성적이 1위보다 좋아야 함 / 불가능 (count : 3)
  7 3 <- Break

C++ Code

#include <iostream>
#include <algorithm>
using namespace std;

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

    int t;
    cin >> t;
    while (t--) {
        int n;
        pair<int, int> p[100001];

        cin >> n;
        for (int i = 0; i < n; ++i) {
            cin >> p[i].first >> p[i].second;
        }

        sort(p, p + n);

        int ans = 1;
        int temp = p[0].second;
        for (int i = 1; i < n; ++i) {
            if (p[i].second < temp) {
                ans++;
                temp = p[i].second;

                if (temp == 1) {
                    break;
                }
            }
        }
        cout << ans << '\n';
    }

    return 0;
}