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문을 돌릴 경우 최악의 상황에 이 될 수 있다. j의 범위를 i를 이용해 제한해줬지만 정렬도 사용하기 때문에 시간 초과가 발생하는 것이 아닌가 싶다.

때문에 이중 for문이 아닌 다른 방법을 사용해야 한다.

정렬을 한 상태에서 다시 생각해보자.

예제 1	예제 2
1, 4	1, 4
2, 3	2, 5
3, 2	3, 6
4, 1	4, 2
5, 5	5, 7
	6, 1
	7, 3

예제에 나와있는 입력을 테스트 케이스에 따라 나눠 정렬했다. 위에서 아래로 순차적으로 확인한다고 생각해보자.

• 예제 1을 확인해보자.

1. 두 번째 값은 3이고, 이전 값 4와 비교했을 때 더 작기 때문에 합격할 수 있다.
2. 세 번째 값은 두 번째 값과 비교했을 때 더 작기에 마찬가지로 합격이다.

• 예제 2를 확인해보자.

1. 두 번째 값은 5이고 첫 번째 값은 4이다. 두 번째 값이 더 크기 때문에 합격하지 못한다.
2. 세 번째 값을 비교해야 한다. 이때, 두 번째 값이 통과하지 못한 경우 비교해야 할 대상은 여전히 첫번째 값이다.

예시를 통해 확인한 것은, 서류 심사 등수가 높은 사람의 면접 등수와 비교한다는 것, 비교했을 때 합격한다면 비교 대상이 합격한 사람으로 변경된다는 것이다. 때문에 이에 따라 인덱스를 설정해 비교 대상을 변경해주면 된다.

#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);
 
        int idx = 0;
        for(int i = 1; i < N; i++){
            if(rank[i].second < rank[idx].second){
                res++;
                idx = i;
            }
        }
        cout << res << '\n';
    }
 
    return 0;
}