[Programmers] 선입 선출 스케줄링

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/12920

코딩테스트 연습 - 선입 선출 스케줄링

우선순위 큐를 이용하면 쉽게 풀 수 있을 것 같은 문제이지만 주어진 조건의 범위가 크기 때문에 힙을 이용할 경우 시간 초과가 발생하는 문제입니다.

해당 문제는 코어 당 작업을 처리하는 시간을 기준으로 최소 시간과 최대 시간을 구하여 해당 범위 내 파라메트릭 서치 기법을 이용하여 풀어야 시간제한 내 AC를 받을 수 있는 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. n이 코어 개수 이하일 경우 작업이 순차적으로 배치되므로 답은 n입니다.

2. 작업 시간이 가장 적게 걸리는 코어와 가장 오래 걸리는 코어를 구하여 해당 코어들만 이용했을 때 소요되는 최소 시간과 최대 시간을 구해줍니다.

3. 2번에서 구한 최소 시간과 최대 시간을 기준으로 파라메트릭 서치를 진행합니다.

3.1 변수 설명

• mid: 현시점
• workCnt: mid 시간 전까지 한 작업량
• curWorkCnt: mid 시점에 한 작업량
• sum: workCnt와 curWorkCnt의 합을 저장한 변수

3.2 파라메트릭 서치 분기 처리

• workCnt가 n 이상일 경우: mid 시점에 처리한 작업량을 합치지 않았는데도 n 이상이므로 시점을 앞당김
• sum이 n 미만일 경우: 시점을 뒤로 미뤄야 함
• sum이 n 이상인 경우: 정답을 구할 수 있는 구간
  • mid 시점에 작업을 할당받은 코어 중 n개가 되는 시점의 코어가 정답
  • 코어는 0-index가 아닌 1-index인 점을 주의

 

	#include <string>
	#include <vector>
	#include <queue>
	#include <algorithm>
	#include <iostream>
	using namespace std;
	const int MAX = 1e5;
	int solution(int n, vector<int> cores) {
	if (n <= cores.size())
	{
	return n;
	}
	int size = cores.size();
	int minCore = MAX;
	int maxCore = 0;
	for (int core : cores)
	{
	minCore = min(minCore, core);
	maxCore = max(maxCore, core);
	}
	int left = minCore * (n / size);
	int right = maxCore * n;
	while (left <= right)
	{
	int mid = (left + right) / 2;
	int workCnt = size;
	int curWorkCnt = 0;
	for (int core : cores)
	{
	workCnt += (mid / core);
	if (mid % core == 0)
	{
	workCnt--;
	curWorkCnt++;
	}
	}
	int sum = workCnt + curWorkCnt;
	if (workCnt >= n)
	{
	right = mid - 1;
	}
	else if (sum < n)
	{
	left = mid + 1;
	}
	else
	{
	for (int i = 0; i < size; i++)
	{
	if (mid % cores[i] == 0)
	{
	workCnt++;
	}
	if (workCnt == n)
	{
	return i + 1;
	}
	}
	}
	}
	return 0;
	}
	int main(void)
	{
	int n = 6;
	vector<int> cores = { 1, 2, 3 };
	cout << solution(n, cores) << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경: Programmers IDE

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~