[백준 1946번] 신입 사원 (C++)

문제링크 : https://www.acmicpc.net/problem/1946

1946번: 신입 사원

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

vector<pii> v;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    int T, N;
    cin >> T;
    while(T--)
    {
        cin >> N;
        for(int i=0; i<N; i++)
        {
            int a, b; //서류, 면접
            cin >> a >> b;
            v.push_back({a, b});
        }
        sort(v.begin(), v.end()); //서류 순위로 정렬
        int result = 1, idx = 0;
        for(int i=1; i<N; i++)
        {
            if(v[idx].second > v[i].second) //면접 순위 체크
            {
                result++;
                idx=i;
            }
        }
        cout << result << "\n";
        v.clear();
    }
    

    return 0;
}

서류 면접에 대해 같이 벡터로 넣어주고 이를 정렬을 해준다.

서류가 앞에 있으므로 서류를 기준으로 정렬된다.

3 2
1 4
4 1
2 3
5 5

1 4
2 3
3 2
4 1
5 5

위와 같이 정렬된 것을 확인할 수 있는데, 우리가 확인해야 할 것은 면접의 순위이다.

하나라도 상대보다 순위가 높은 것이 있으면 되기에 서류 1등의 면접 등수보다 높은 등수를 가진 사람이 있다면 그 사람은 조건을 만족하는 것이다.

 

이렇게 조건 만족하는 사람으로 인덱스를 옮기고 또 이어서 조건을 만족하는 경우를 찾는다.

위 예시의 경우 처음 1, 4 ->  2, 3으로 이동했는데 이제 면접 순위 3등보다 높은 순위를 가진 사람을 찾으면 된다.

이를 계속해서 탐색하며 조건이 맞을때 마다 인덱스 이동과 동시에 카운팅을 해주면된다.