BaekJoon 1946번: 신입 사원(C++)

https://www.acmicpc.net/problem/1946

1946번: 신입 사원

풀이법

1) 정렬을 활용한 그리디 알고리즘으로 해결할 수 있었으나, 풀이에 오랜시간 걸렸던 문제이다.

2) 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 지키기 위해서, 서류 심사 성적을 기준으로 들어온 값을 정렬 하였다.

<정렬 전>				<정렬 후>
  3 6					  1 4
  7 3					  2 5
  4 2					  3 6
  1 4					  4 2
  5 7					  5 7
  2 5					  6 1
  6 1					  7 3

3) 해당 정렬이 완료된 후, 맨 처음 인자의 면접시험 값을 기준으로 해당 등수보다 낮은 지원자가 나타날 경우, 비교 값을 해당 지원자의 면접 등수로 바꾸어 주었고, 이를 반복하여 탐색을 진행했다. 

(서류 심사 기준으로 오름차순 정렬하게 되면, 뒤의 지원자의 서류 심사 점수는 무조건 앞 지원자보다 낮게 된다. 이 경우 조건을 만족시키기 위해서 앞 지원자 보다 면접 점수가 높아야 된다는 점을 이용하였다.)

 

#include <string>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#include <unordered_map>
#include <math.h>
#include <stack>
#include <map>
using namespace std;
int t;
int n;
bool compare(pair<int, int> a, pair<int, int> b)
{
	if (a.first < b.first)
		return true;
	else
		return false;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> t;
	while (t > 0)
	{
		cin >> n;
		vector<pair<int, int>> vec;
		for (int i = 0; i < n; i++)
		{
			int a, b; cin >> a >> b;
			vec.push_back({ a,b });
		}
		sort(vec.begin(), vec.end());
		int temp = 1;
		int comp = vec[0].second;
		for (int i = 1; i < n; i++)
		{
			if (vec[i].second < comp)
			{
				comp = vec[i].second;
				temp++;
			}
		}
		cout << temp << "\n";
		t--;
	}
}