신입 사원 (백준 - 1946번)

그리디 알고리즘 문제이다.

 

모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다. 예를 들어 A의 지원자가 B 지원자보다 서류 심사나 면접시험 중 하나라도 더 높다면 선발이 되고, 둘 다 낮다면 절대 선발되지 않는다.

 

알고리즘은 다음과 같다.

1. 우선 서류 전형 순위를 오름차순으로 정렬한다.
2. 정렬 후 가장 첫번째에 있는 사원은 조건에 무조건 만족하므로 선발한다.
3. 선발된 사원의 면접 순위를 N에 기록하고 다른 지원자들의 면접 점수를 검사한다. 
   
   
4. 만약 지원자의 면접 순위가 N보다 작은 경우 조건에 만족하므로 선발하고 순위를 다시 N에 기록한다.

코드는 다음과 같다.

 

#include <iostream>
#include <algorithm>
using namespace std;

struct employeeRank
{
	int first;
	int second;
};

bool cmp(employeeRank& a, employeeRank& b)
{
	return a.first < b.first;
}

int main()
{
	int testCaseCount = 0;
	cin >> testCaseCount;

	employeeRank** Infos = new employeeRank*[testCaseCount];
	int* maxEmployee = new int[testCaseCount];

	for (int i = 0; i < testCaseCount; ++i)
	{
		int employeeCount = 0;
		cin >> employeeCount;

		Infos[i] = new employeeRank[employeeCount];

		for (int j = 0; j < employeeCount; ++j)
		{
			// 순위 입력
			cin >> Infos[i][j].first >> Infos[i][j].second;
		}

		// 서류전형 순위를 정렬을 한다.
		sort(Infos[i], Infos[i] + employeeCount, cmp);

		// 첫번째는 무조건 선발
		maxEmployee[i] = 1;
		// 첫번째 지원자의 면접전형 순위를 기록해놓는다.
		int tmpRank = Infos[i][0].second;

		// 다른 지원자의 면접 전형 순위가 더 높을 경우 채용한다.
		for (int j = 1; j < employeeCount; ++j)
		{
			if (Infos[i][j].second < tmpRank)
			{
				++maxEmployee[i];
				tmpRank = Infos[i][j].second;
			}
		}
	}

	for (int i = 0; i < testCaseCount; ++i)
	{
		cout << maxEmployee[i] << endl;
		delete[] Infos[i];
	}

	delete[] Infos;
	delete[] maxEmployee;
}