- 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문을 돌릴 경우 최악의 상황에
때문에 이중 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을 확인해보자.
- 두 번째 값은 3이고, 이전 값 4와 비교했을 때 더 작기 때문에 합격할 수 있다.
- 세 번째 값은 두 번째 값과 비교했을 때 더 작기에 마찬가지로 합격이다.
- 예제 2를 확인해보자.
- 두 번째 값은 5이고 첫 번째 값은 4이다. 두 번째 값이 더 크기 때문에 합격하지 못한다.
- 세 번째 값을 비교해야 한다. 이때, 두 번째 값이 통과하지 못한 경우 비교해야 할 대상은 여전히 첫번째 값이다.
예시를 통해 확인한 것은, 서류 심사 등수가 높은 사람의 면접 등수와 비교한다는 것, 비교했을 때 합격한다면 비교 대상이 합격한 사람으로 변경된다는 것이다. 때문에 이에 따라 인덱스를 설정해 비교 대상을 변경해주면 된다.
#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;
}