BOJ 1946 신입 사원 C++

문제

입력이 점수가 아닌 순위라는 점에 유의한다.

 

접근 방법

🌟 N이 최대 100,000임을 보아 이중 for문은 좋은 해결책이 아닐 것이다.

🌟 둘 중 하나라도 1등인 지원자는 무조건 합격임을 생각하면 어떻게 시작하면 될지 알 수 있을 것이다.

 

나는 이렇게 해결했다. 시간 복잡도는 O(N)이다.

1. 지원자의 서류 순위, 면접 순위를 쌍으로 묶어 저장한다.
2. 서류 순위를 기준으로 오름차순 정렬한다. (혹은, 반대로 해도 상관 없다.)
3. 1등의 면접 순위를 기준으로 잡는다.
4. 지원자를 순회하며 기준으로 잡은 면접 순위보다 좋다면(숫자가 작다면) 합격 처리하고, 새 기준으로 잡는다.

 

코드

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

int main(void) {
    int T; cin >> T;
    while(T--) {
        int N; cin >> N;
        vector<pair<int,int>> candidates(N);
        for(int i = 0; i < N; i++) {
            cin >> candidates[i].first >> candidates[i].second;
        }
        
        sort(candidates.begin(), candidates.end());
        int lowest = candidates[0].second;
        int passed = 1;
        for(int i = 1; i < N; i++) {
            if(lowest < candidates[i].second)
                continue;
            passed++;
            lowest = candidates[i].second;
        }
        cout << passed << '\n';
    }
}