이 문제에선 테스트 케이스가 2개가 있어서 어떻게 풀어야 하는지 감이 바로 잡혔다.
각각의 사원에 대해 최대의 경우의 수가 각각 n-k 개가 나오게 되므로
모든 사원의 경우의 수는 (n-1)*n / 2 이다.
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
if (score[i].second > score[j].second)
{
count--;
break;
}
}
}O(N^2) 이라 안될줄은 알았는데 도저히 방법이 생각이 안나 구글링을 했다.
이번 문제를 통해 배운 게 있다면, 회의실배정(1931)이나 이 문제처럼
N=100,000 인 경우 O(N^2)인 코드가 있으면 안 되므로
기준이 되는 변수를 잡아준다.
첫 시험 등수가 낮은 순대로 배열했으니, 첫번째 사원은 시험하나가 1등이니깐 무조건 합격이다.
그러니 얘를 기준으로 잡는다.
int bound = score[0].second;
한명한명 비교할 때 마다 'bound'는 bound와 비교대상의 두번째 성적과 비교하여 최솟값으로 갱신된다.
이렇게 되면 O(N)으로 줄어들게 되고 정렬하는데 사용되는 O(NlogN) 도 시간안에 들어오므로 코드를 완성할 수 있게 된다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(const pair<int, int>& p1, const pair<int, int>& p2) { return p1.first < p2.first; }
int min_(int a, int b) { return a < b ? a : b; }
int main()
{
int T; int a, b;
vector<pair<int, int>> score;
cin >> T;
while (T--)
{
int n;
cin >> n;
score.clear();
for(int i=0;i<n;i++)
{
cin >> a >> b;
score.push_back({ a,b });
}
sort(score.begin(), score.end(), cmp);
int count = n;
int bound = score[0].second;
for (int k = 1; k < n; k++)
{
if (bound < score[k].second) {count--;}
bound = min_(bound, score[k].second);
}
cout << count <<"\n";
}
return 0;
}
ㅎㅅㅇ