[BOJ / C++] #1946 신입 사원

👀문제 풀이

서류성적과 면접성적중 어느것 하나라도, 다른 모든 사원보다 순위가 높아야 하므로, 서류성적을 기준으로 오름차순 정렬해놓고, 면접성적을 따진다.

👀처음 코드

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

int main(){

    int T;
    cin>>T;
    while(T){
        int N;
        vector<pair<int,int>> score; // (서류, 면접)
        cin>>N;
        int cnt=N;
        for(int i=0;i<N;i++){
            int a,b; cin>>a>>b;
            score.push_back(make_pair(a,b));
        }

        sort(score.begin(), score.end()); // 서류 순위순으로 정렬

        for(int i=N-1;i>=0;i--){
            for(int j=i-1;j>=0;j--){ // 서류 꼴지부터, 그 윗 순위들의 면접점수를 봄
                // 서류는 이미 다른 지원자보다 낮음
                // 면접이 다른 모든 앞 지원자보다 커야 함
                int interviewScore=score[i].second;
                if(interviewScore>score[j].second) {
                    cnt--;
                    break;
                }
            }
        }

        cout<<cnt;
        T--;
    }
}

오름차순 정렬해놓고, 순위가 낮은 사원부터 그 앞 순위 사원들을 거꾸로 따져가며 2중 for문을 돌렸더니 시간초과로 틀려버렸다.

👀개선 코드

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

int main(){

    int T;
    cin>>T;
    for(int t=0;t<T;t++){
        int N;
        vector<pair<int,int>> score; // (서류, 면접)
        cin>>N;

        for(int i=0;i<N;i++){
            int a,b; cin>>a>>b;
            score.push_back(make_pair(a,b));
        }

        sort(score.begin(), score.end()); // 서류 순위순으로 정렬

        int cnt=1;
        int interviewScore=score[0].second; //1위의 면접 점수

        // 그 뒤에부턴, 면접 점수가 무조건 더 높아야 채용
        for(int i=1;i<N;i++){
            if(score[i].second<interviewScore){
                cnt++;
            }
            // 제일 높은 순위로 업데이트
            interviewScore=min(score[i].second, interviewScore);
        }

        cout<<cnt<<"\n";
    }

    return 0;
}

서류 성적 기준으로 정렬을 했으므로, 0인덱스부터 서류성적이 높은 순으로 들어가있다.
따라서 1인덱스부터 ~N-1 까지 보면서, 면접 성적은 순위가 높은 지원자 중 가장 높은 면접 순위보다 더 높아야한다.
따라서 가장 높은 순위의 면접 성적을 계속 업데이트 하면서 살펴본다.