이번 문제는 프로그래머스의 레벨 3 선입 선출 스케줄링이다.
문제가 굉장히 짧지만, 차근차근 읽어보도록 하자.

먼저 최대 10000개의 코어와 함께 처리시간이 배열로 주어진다.
각 코어의 처리시간은 최대 10000시간 까지 주어진다.
또한 일의 개수가 최대 50000개 주어진다.
각 코어가 일을 모두 끝낼 수 있는 최적의 경우로 일을 했을 때,
가장 마지막 작업을 처리하게 되는 코어의 번호를 출력하라!

어떻게 문제를 풀어야 할까?

Greedy?

가장 먼저 든 생각은 그리디하게 풀 수 있지 않을까? 였다.
그리디하게 종료 시간이 짧은 코어 부터 선택 하는 것이다.
그리디하게 앞에서 부터 작업을 처리하며 차례차례 구현한 다음,
마지막 작업을 수행하는 코어의 인덱스를 직접 찾는 것이다.

직접 찾으려면 시간 초과가 발생하지는 않을까?
효율적인 로직을 위해 Queue 자료 구조를 한 번 이용해보자.

우선순위 큐에 현재 진행 중인 작업을 집어 넣고, 현재 시간과 종료 시간을 비교한다.
종료 시간이 현재 시간과 같다면? 그냥 작업을 종료하면 된다.
큐에서 빠지게 되면, 동시에 새로운 일을 수행할 수 있다는 것!
곧바로 해당 코어에게 새로운 일을 배정하고, 큐에 다시 집어 넣는다.

종료 시간이 현재 시간보다 크다면? 작업을 종료하되, 시간을 갱신한다.
이후 동일하게 새로운 일을 배정하고 큐에 다시 집어 넣는다!

단, 우선순위 큐는 종료 시간을 기준으로 오름차순으로 정렬하도록 한다.
위와 같이 반복적으로 처리하면, 마지막에 큐에 남는 코어가 답이 될 것이다.
아래와 같이 구현해보았다.

int solution(int n, vector<int> cores) {
	int answer = 0;
	int size = cores.size();

	priority_queue<pii, vector<pii>, greater<>> core_q;
	for (int i = 0; i < cores.size(); i++) {
		core_q.push({cores[i], i});
		n--;
	} // 시작하자마자, 모든 코어에 작업을 시킴

	int timer = 1;
	while (n > 0) {
		pii curr_core = core_q.top();
		core_q.pop(); // 다음 작업을 처리할 코어

		if (curr_core.first == timer)
			n--; 
		// 현재 시간과 해당 코어의 종료 시간이 같으면 그냥 종료
		else if (curr_core.first > timer) {
			timer = curr_core.first;
			n--;
		// 현재 시간보다 해당 코어의 종료 시간이 크면?
		// 현재 시간을 코어의 종료 시간으로 변경해야 함
		}

		if (n == 0)
			answer = curr_core.second + 1;
		// 작업이 모두 끝났으면 종료 시점 저장
		else
			core_q.push({ timer + cores[curr_core.second], curr_core.second });
	}

	return answer;
}

이분 탐색

안타깝게도 위의 로직은 효율성 케이스에서 시간 초과가 발생했다.
정확성 케이스는 모두 통과했으나, 아무래도 edge case를 통과하지 못하나보다.
edge case의 경우, O(10000 * 50000)의 시간 복잡도를 갖게 될텐데,
문제의 시간 제한을 통과하기엔 너무 느린 속도였던 것 같다.
그래서 다른 사람들의 풀이를 조금 참고해보았다.

효율성 케이스를 통과하기 위해서는 이분 탐색 을 해야 한다고 한다.
어떤 요소를 옮기며 이분 탐색을 진행해야 할까?

정해져 있는 요소는 작업의 수 n과 처리 시간, 코어의 수이다.
그럼 우리가 조절할 수 있는 유일한 변수는 작업 시간이 된다.
주어지는 작업 시간 내에 n개의 작업을 처리할 수 있는지로 기준을 잡자.

처리가 가능하다면, 작업 시간을 더 줄여보고
처리가 불가능하다면, 작업 시간을 더 늘려보면 될 것 같다.
처리가 가능한지 판단하는 로직은 아래와 같이 구현하면 될 것이다.

int std = cores.size();
for (int i = 0; i < cores.size(); i++)
	std += mid / cores[i];

오른쪽 끝이 되는 최대 작업 시간은 몇으로 잡아야 할까?
원래는 edge case인 (100000 * 50000) / 2가 최대 시간이 된다.
하지만 50000으로 잡아도 통과를 하는 것을 보니, 케이스가 없나보다.

이제 코어를 순회하며 각 코어가 처리할 수 있는 일의 수를 계산한다.
총 작업 시간 / 처리 시간 + 1을 하면, 처리할 수 있는 일의 수가 된다.
아래의 그림을 보면 이해가 빠를 것이다.

image

위의 그림은 7초동안 3개의 코어가 처리할 수 있는 작업의 수이다. (7 / 1) + 1 + (7 / 2) + 1 + (7 / 3) + 1의 결과인 14임을 알 수 있다. +1은 기본적으로 0초에 수행되는 작업들을 의미한다. 이 로직을 n`개를 처리하지 못하는 최대 시간에 수렴할 때까지 반복한다.

왜 n개를 만들지 못하는 최대 시간에 수렴시킬까?
그래야 해당 시간 + 1을 했을 때, n개를 처리할 수 있기 때문이다.
이제 우리는 남은 일을 처리하는 과정에서 답을 구할 수 있다.

해당 시간 + 1 / 처리 시간의 나머지가 0인 코어는 일을 처리할 수 있다.
왜? 처리 시간으로 나누어 떨어지는 시간에 코어는 작업 + 1이 되기 때문!
최종적으로 아래와 같이 구현할 수 있다.

int solution(int n, vector<int> cores) {
	int answer = 0;

	if (n <= cores.size())
		return n;

	int left_v = 0, right_v = 50000;
	while (left_v + 1 < right_v) {
		int mid = (left_v + right_v) / 2;
		int std = cores.size(); // 기본적으로 진행하는 작업

		for (int i = 0; i < cores.size(); i++)
			std += mid / cores[i];
		// 작업 시간 내에 해당 코어가 몇 개의 작업을 처리할 수 있는지?

		if (std < n)
			left_v = mid;
		// 작업을 모두 끝낼 수 없다면 작업 시간을 늘려야 한다.
		else
			right_v = mid;
		// 작업을 모두 끝낼 수 있다면 작업 시간을 줄인다.
	}

	int std = cores.size(); // 기본 작업
	for (int i = 0; i < cores.size(); i++)
		std += left_v / cores[i];
	// 최대 시간 내에 처리할 수 있는 작업의 수
	for (int i = 0; i < cores.size(); i++) {
		if ((left_v + 1) % cores[i] == 0)
			std++;
	// 최대 시간 + 1을 했을 때 처리가능한 코어를 찾는다.
		if (std == n)
			return i + 1;
	}

	return 0;
}

해당 문제를 딱 보았을 때, 이분 탐색일 줄은 꿈에도 몰랐다.
이런 유형의 아이디어성 문제는 많이 풀어서 익혀야 한다.
좀 더 많은 문제를 풀도록 하자.