[백준 - 1946] 신입 사원 [C++]

1. 문제

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

1946번: 신입 사원

 

2. 풀이

그리디 문제이다.

일단 n이 10만이므로 O(n^2) 으로는 풀 수 없다.

그래서 우선 서류순으로 정렬하고, 

1번째 지원자는 서류로 1등이니 반드시 뽑힌다.

2번째 지원자부터는 면접순위를 비교하면서 세줬다.

어떤 지원자가 서류점수는 낮더라도(정렬되어있으니 당연히 낮음) 현재까지의 최고 면접 순위보다 높은경우 

그 지원자를 선발하고 key를 교체한다.

 

3. 코드

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

using namespace std;
int T;
int n;

class Applicant {
public:
    int documentRank;
    int interviewRank;
    Applicant() {}
    Applicant(int d, int i) : documentRank(d), interviewRank(i) {}
};

bool compare(const Applicant& a, const Applicant& b) {
    return a.documentRank < b.documentRank;
}

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

    cin >> T;
    for(int t = 0; t < T; t++) {
        cin >> n;
        vector<Applicant> applicantList(n);
     
        for(int i = 0; i < n; i++) {
            int d, in;
            cin >> d >> in;
            applicantList[i] = Applicant(d, in);
        } 

        sort(applicantList.begin(), applicantList.end(), compare);

        int ans = 1;  // 첫 번째 지원자는 반드시 선발됩니다.
        int key = applicantList[0].interviewRank;  // 첫 번째 지원자의 면접 순위를 key로 설정

        for(int i = 1; i < n; i++) {
            if(applicantList[i].interviewRank < key) {
                ans++;
                key = applicantList[i].interviewRank;  // key 갱신
            }
        }

        cout << ans << "\n";
    }

    return 0;
}