프로그래머스 선입 선출 스케줄링 [Lv. 3] (C++)

프로그래머스

CPU에는 여러개의 코어가 있습니다. 각 코어의 작업 속도를 배열로 입력받을 때, N번째 일감을 처리하는 코어의 번호를 찾아주세요.

 

풀이 방법

이 문제는 이진 탐색으로 풀이하는 문제입니다.

int start = -1;
int end = 1000000;

// N이 코어 수 보다 작다면 바로 출력
if (n <= cores.size())
    return n;

while (start + 1< end)
{
    int mid = (start + end) / 2;

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

    if (total < n)
        start = mid;
    else 
        end = mid;
}

특정 시간동안 몇개의 작업을 처리할 수 있는지 계산하여 최종적으로 N개의 작업을 처리하기 위해 필요한 시간을 찾아줍니다.

 

int total = cores.size();
for (int i = 0; i < cores.size(); i++)
    total += start / cores[i];
for (int i = 0; i < cores.size(); i++)
{
	// 현재 시간에 작업 처리를 시작한거라면 total ++
    if ((start+1) % cores[i] == 0)
        total++;
    // 처리한 작업의 총량이 N과 같다면 코어의 번호를 출력
    if (total == n)
        return i + 1;
}

찾은 시간을 바탕으로 코어의 수 만큼 순회하여 N번째 작업을 처리하는 지점을 찾아주면 됩니다.

 

 

정답 코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int solution(int n, vector<int> cores) {
    int start = -1;
    int end = 1000000;
    
    if (n <= cores.size())
        return n;
    
    while (start + 1< end)
    {
        int mid = (start + end) / 2;
        
        int total = cores.size();
        for (int i = 0; mid > 0 && i <cores.size(); i++)
            total += mid / cores[i];
        
        if (total < n)
            start = mid;
        else 
            end = mid;
    }    
    
    int total = cores.size();
    for (int i = 0; i < cores.size(); i++)
        total += start / cores[i];
    for (int i = 0; i < cores.size(); i++)
    {
        if ((start+1) % cores[i] == 0)
            total++;
        if (total == n)
            return i + 1;
    }
    
    return -1;
}