프로그래머스 - 선입 선출 스케줄링 [C++]

이 문제는 이분 탐색을 이용해서 풀었다.

 

이 문제를 어렵게 만드는 요인은 마지막 작업이 들어가는 코어의 번호를 찾는 것이다.

 

일단 n이 core의 size보다 작거나 같으면 0시간 후일 때, 즉 아직 시작하지 않았을 때 코어에 모두 들어가게 되므로 base case에 해당한다.

 

n이 core의 size보다 클 때부터 문제가 시작된다. 우선 처음에 모든 코어에 작업이 들어가므로 코어의 수만큼 n에서 빼준다.

그 다음 시간에 대해서 이분 탐색을 수행한다. 이 이분 탐색의 목적은 우리가 찾고자 하는 작업이 들어가지는 최소의 시간을 찾기 위함이다. 즉, lower bound를 찾는 것과 동일하다.

해당 시간을 찾았으면, 이전 시간의 배열을 구해 해당 시간 배열과 빼준다. 그러면 1 0 1 0 1 1 ... 이런 식으로 1과 0으로만 존재하게 되는데, 여기서 1은 해당 시간에 작업이 끝나서 새로운 작업을 받아야 하는 상태임을 의미하게 된다.

따라서 순차적으로 돌면서 순번에 맞는 코어를 찾으면 바로 리턴하는 방식으로 문제를 풀 수 있었다.

 

주의할 점은 calculate 함수에서 극단적으로 mid가 5억이고, 모든 코어의 처리 시간이 1이라면 int로는 오버플로우가 나게 된다. 따라서 이 부분만을 long long으로 바꿔주어야 한다. 만약 귀찮아서 모두 long long으로 바꾸면 시간 초과가 나게 된다.

 

시간 초과가 나는 이유를 정확히는 모르지만, long long은 캐시 히트가 떨어져 속도가 저하된다는 글을 보았다.

#include <string>
#include <vector>

using namespace std;

typedef long long ll;

ll calculate(int mid, vector<int> cores)
{
    ll result = 0;
    for (int core : cores)
    {
        result += mid / core;
    }
    return result;
}

int lowerBound(int n, vector<int> cores)
{
    ll dest = n;
    int left = 0;
    int right = 500000000;
    int result = -1;
    
    while (left <= right)
    {
        int mid = (left + right) / 2;
        
        if (calculate(mid, cores) >= dest)
        {
            result = mid;
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
    }
    
    return result;
}

vector<int> getArr(int time, vector<int> cores)
{
    vector<int> result;
    
    for (int core : cores)
    {
        result.push_back(time / core);
    }
    
    return result;
}

int solution(int n, vector<int> cores) {
    if (n == 0)
    {
        return 1;
    }
    
    if (n <= cores.size())
    {
        return n;
    }
    
    n -= cores.size();
    
    int time = lowerBound(n, cores);
    vector<int> present = getArr(time, cores);
    vector<int> prev = getArr(time - 1, cores);
    ll prevCnt = calculate(time - 1, cores);
    
    int size = present.size();
    for (int i = 0; i < size; i++)
    {
        present[i] -= prev[i];
    }
    
    ll answer = prevCnt;
    for (int i = 0; i < size; i++)
    {
        answer += present[i];
        if (answer == n)
        {
            return i + 1;
        }
    }
    
    return answer;
}