BOJ 1946, 신입 사원
ProblemSolving ·이 문제는 정렬을 이용한 문제입니다.
풀이
정렬을 이용하지 않고 단순히 이중포문을 이용하여 답을 구하게되면 20 X10만 X 10만 으로 2초안에 실행할 수 없습니다.
하지만 오름차순으로 정렬을 해준다면 input[i].first에 점점 순위가 낮은 값들이 정렬이 되겠죠.
그렇다면 한 번의 포문으로 답을 구해낼 수 있습니다.
순위가 낮은 친구들은 자기보다 순위가 높은 친구들을 포함해서 second에서 가장 높은 순위를 가져야 선발 자격을 갖출 수 있겠죠?
포문을 돌아 최솟값을 갱신할 때마다 ans++를 해주시면 답을 구하실 수 있습니다.
#include<iostream>
#include<algorithm>
using namespace std;
int t,n,ans,chk;
pair<int, int> input[100001];
int main()
{
cin >> t;
while (t--)
{
cin >> n;
int ans = 0;
int Min = 1e9;
for (int i = 0; i < n; i++)
cin >> input[i].first >> input[i].second;
sort(input, input + n);
for (int i = 0; i < n; i++)
if (Min > input[i].second)
ans++, Min = input[i].second;
printf("%d\n", ans);
}
return 0;
}