[백준] 1946 신입사원 c++

 

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

KEY

• 그리디 유형의 문제의 상당 부분은 정렬을 통해서 풀 수 있는데, 이 문제 역시 벡터의 정렬을 통해 해결할 수 있다.
• 서류순위, 면접순위 두 가지를 고려해야 하므로 서류순위를 오름차순으로 정렬하여 고정한 후, 면접 순위만을 고려하면 된다.
• 서류순위를 오름차순 정렬했기 때문에 면접순위를 고려할 때, n번째 신입사원은 1 ~ n-1번째 신입사원의 면접순위보다 높아야 한다. 

 

Code

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
#include<string>
using namespace std;
int T, N;
int main() {
    cin >> T;
    while (T--) {
        //초기화
        int answer = 0; //정답
        vector<pair<int, int>> v; //{서류순위, 면접순위}
        priority_queue<int, vector<int>, greater<>> pq; // 면접순위의 최소값 식별을 위한 우선순위 큐
 
        cin >> N;
        for (int i = 0; i < N; i++) {
            int first, second;
            cin >> first >> second;
            v.push_back({ first,second });
        }
        sort(v.begin(), v.end()); //서류 순위대로 정렬
 
        for (int i = 0; i < N; i++) {
            pq.push(v[i].second);
            if (v[i].second <= pq.top()) { //신입사원의 면접순위가 여태 나온 면접순위의 최솟값보다 작다면
                answer++;
            }
        }
        cout << answer << endl;
    }
}