2023-08-17-newcomer-1946

• toc {:toc}

문제 확인하기

풀이

문제 이해가 쉽사리 되지 않지만 차근차근 읽어보면 두 시험 성적 등수가 주어지고, 어떤 지원자 A, B 를 비교했을 때 A 의 등수가 1, 4 이고 B 의 등수가 2, 5 인 경우 B 는 합격할 수 없다. 입력은 서류 심사 등수, 면접시험 등수 순으로 들어온다.

• 두 시험 성적을 모두 비교해야 한다. ⇒ 복잡하다.
  • 하나를 고정시키자. ⇒ 서류 심사 등수를 정렬한다.
• 면접시험의 등수를 비교한다.
  • 이중 for 문을 사용해 서류 심사 등수 1 등부터 N 등까지 비교한다.

다음의 아이디어를 가진 채 코드를 구현했다.

#include <bits/stdc++.h>
using namespace std;
 
bool compare(const pair<int, int>& a, const pair<int, int>& b){
    return a.first < b.first;
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    int T, N, is_pass = 1;
    pair<int, int> rank[100005];
 
    cin >> T;
 
    while(T--){
        int res = 1;
        cin >> N;
        for(int i = 0; i < N; i++){
            cin >> rank[i].first >> rank[i].second;
        }
        sort(rank, rank+N, compare);
 
        for(int i = 1; i < N; i++){
            is_pass = 1;
            for(int j = 0; j < i; j++){
                if(rank[i].second > rank[j].second){
                    is_pass = 0;
                    break;
                }
            }
            if (!is_pass) continue;
            else res++;
        }
        cout << res << '\n';
    }
 
    return 0;
}

하지만, 시간 초과가 떴다. N 이 100,000 개 이기 때문에 이중 for 문을 돌릴 경우 최악의 상황에