문제
정답
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(pair<int, int> &p1, pair<int, int> &p2){
return p1.first < p2.first;
}
int meeting(vector<pair<int, int>> &v){
int ans = 1; //서류 1위의 선발
int min = v[0].second; //서류 1위의 면접 결과
for(int i=1; i<v.size(); i++){
if(v[i].second < min) //지원자의 면접 순위가 더 높다면
{
ans++;
min = v[i].second;
}
}
return ans;
}
int main()
{
int t, n;
cin >> t;
while(t--){
vector<pair<int, int>> v;
int a, b;
//input
cin >> n;
for(int i=0; i<n; i++){
cin >> a >> b;
v.push_back(make_pair(a, b));
}
//정렬
sort(v.begin(), v.end(), compare);
//면접 순위 비교
cout << meeting(v) << "\n";
}
return 0;
}- 무난했다. pair로 서류와 면접 순위를 묶는 게 중요한...?
- 혼자 힘으로 푼 문제라 각별하다!
생각의 흐름
언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다.
전형 짧고 대규모 채용.. 진짜 부럽다...... 나도 누가 데려가주라 그러려면 코테 열심히 준비하자...!!!!
서류-면접 순서 순위
3 2
1 4
4 1
2 3
5 5
서류를 기준으로 정렬하면
1 4
2 3
3 2
4 1
5 5
일단 서류 1위는 무조건 선발.
1위와 2위를 비교했을 때 2위는 1위보다 면접이 높으니 선발.
3위는.. 2위보다 면접이 높으니 선발
4위는.. 면접 1등이니까 선발
5위는.. ... 탈락. 면접이 타인보다 높아야하는데 갱신된 최댓값(=1위)보다 낮다.
결론을 정리하자면,
- 서류 순위대로 정렬 후 면접 순서를 비교한다.
- 서류 1위의 면접 순위를 min로 설정 후, 다음 순위의 면접 순위가 min보다 작다면 선발. -> min 갱신
- min과 면접 순위를 비교하여 작다면 선발 및 갱신, 크다면 탈락.
검증해보자.
3 6
7 3
4 2
1 4
5 7
2 5
6 1
서류 순위대로 정렬
1 4
2 5
3 6
4 2
5 7
6 1
7 3
min = 4, 1위 선발
2위의 5 > 4이므로 선발 안함, min = 4
3위 : 6 > 4이므로 선발 안함, min = 4
4위 : 2 < 4이므로 선발, min = 2
5위 : 7 > 2이므로 선발 안함, min = 2
6위 : 1 < 2이므로 선발, min = 1
7위 : 3 > 1이므로 이므로 선발 안함, min = 1
선발된 사람은 3.
기억하면 좋을 것
- vector<pair ~~>의 정렬을 할 때, pair.first의 값으로 정렬을 할 거라면 default sort 만으로도 가능하다! (나처럼 compare을 정의할 필요가 없음)
sort(candidates.begin(), candidates.end()); // 서류 심사 순위(first) 순서대로 정렬