백준 1946번: 신입 사원

[문제 링크]

1946번: 신입 사원

---

반복문 횟수를 줄여야 하는데 자꾸 해메서 풀이까지 오래걸린 문제였다.

 

먼저 서류심사 성적을 기준으로 오름차순 정렬을 한 뒤, 서류심사 성적이 더 좋은 지원자들의 면접시험 성적과 서류심사 성적이 안좋은 지원자들의 면접시험 성적을 비교하여 서류심사 성적이 안좋은 지원자의 면접시험 성적이 더 높다면 그 지원자를 뽑는 식으로 구현하였다.

 

이번에도 퀵소트를 직접 구현해보았는데 시간초과가 발생하였다. 

입력받는 성적에서 중복되는 성적이 없고, 범위가 1~N 인 점을 이용하여 최악의 시간복잡도가 O(N)인 정렬 방법을 만들어서 구현하였다.

---

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

/* 시간 초과 발생 ///
void Quick_sort(vector<pair<int, int>>::iterator start, vector<pair<int, int>>::iterator end)
{
	if (start >= end) return;

	vector<pair<int, int>>::iterator pivot = start;
	vector<pair<int, int>>::iterator i = start + 1;
	vector<pair<int, int>>::iterator j = end - 1;

	while (i <= j)
	{
		while (i < end &&  (*i).first <= (*pivot).first)
			i++;
		while (j > start && (*j).first >= (*pivot).first)
			j--;

		if (i > j)
		{
			pair<int, int> temp = *pivot;
			*pivot = *j;
			*j = temp;
		}
		else
		{
			pair<int, int> temp = *i;
			*i = *j;
			*j = temp;
		}
	}

	Quick_sort(start, j);
	Quick_sort(j + 1, end);
}
*/

void DH_sort(vector<pair<int, int>>& data, int start, int end)
{
	int i = start;
	int j = end;

	while (i < j)
	{
		while (1)
		{
			if (data[i].first == i + 1)
			{
				i++;
				break;
			}
			else
			{
				pair<int, int> temp = data[data[i].first-1];
				data[data[i].first - 1] = data[i];
				data[i] = temp;
			}
		}
	}
}

int Greedy(vector<pair<int, int>>& emp, int N)
{
	//Quick_sort(emp.begin(), emp.end()); // 시간초과

	DH_sort(emp, 0, N);

	int ret = 1;
	int index = emp[0].second;
	for (int i = 1; i < N; i++)
		if (index > emp[i].second)
		{
			ret++;
			index = emp[i].second;
		}

	return ret;
}

int main(void)
{
	vector<pair<int, int>> emp;

	int tc;
	cin >> tc;
	while (tc--)
	{
		int N;
		cin >> N;

		for (int i = 0; i < N; i++)
		{
			int a, b;
			cin >> a >> b;
			emp.push_back(make_pair(a, b));
		}

		cout << Greedy(emp, N) << endl;
		emp.clear();
	}

	return 0;
}

알고리즘 200일 프로젝트 - 111 day