C++ / 프로그래머스 / 선입 선출 스케줄링

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12920

프로그래머스

문제풀이

처음에는 문제가 이해가 안 갔다.

• 한 코어에서 작업이 끝나면 작업이 없는 코어가 바로 다음 작업을 수행합니다.

이 부분을 보고 각각의 코어가 각각의 작업을 동시에 할 수 없나?라고 생각을 했다.

그래서 문제에 대한 다른 블로그를 찾아봤더니 동시에 할 수 있는 거였다.

 

두 번째 문제로는 마지막 작업을 처리하는 코어의 번호를 return하라길래 마지막에 혼자 남아 작업하는 코어의 번호를 return 하는 줄 알았는데 아니었다.

가장 늦게 끝나지는 않더라도 마지막에 일을 받은 코어의 번호를 return 하라는 것이었다...

 

문제를 이해하고 나서 우선순위 큐와 큐를 이용해 풀어봤는데 정확성은 다 맞았지만 효율성에서 다 시간초과가 떴다.

그래서 질문글을 보니 파라메트릭 서치를 이용하라 해서 코드를 다시 짰다.

 

이분탐색이든 파라메트릭 서치 문제를 풀 때 도대체 어느 부분을 left, right부분으로 삼아야 하지?라는 생각을 많이 한다.

그리고 문제를 보자마자 이분탐색을 써야 하는구나라는 생각이 떠오르지 않는다...

 

파라메트릭 서치 문제인걸 알고, left, right로 둘 부분을 찾으면 크게 어렵진 않다.

다만 주의할 점이 일의 최대개수는 50,000개, 코어당 작업 처리 시간은 최대 10,000이다.

처음에 right를 낮게 설정해 효율성테스트 4, 5, 6에 실패했었다.

 

만약 n이 코어의 개수 이하라면 n을 정답으로 하면 된다.

left는 1로 설정할 것이기 때문에 left + right를 하는 과정에서 오버플로우를 방지하기 위해 right는 int의 최대범위-1로 설정한다.

 

    while (left <= right) {
        mid = (left + right) / 2;
        cnt = 0;
        div = vector<int>();
        for (idx = 0; idx < cores.size(); ++idx) {
            if (mid % cores[idx] != 0)
                cnt += (mid / cores[idx] + 1);
            else {
                div.push_back(idx);
                cnt += (mid / cores[idx]);
            }
            if (cnt >= n) break;
        }

left와 right는 시간으로 설정했다.

left + right의 절반값인 mid를 각 코어의 처리 시간으로 나누어 개수를 구하였다.

작업을 시작했을 때를 구해야 하기 때문에 나머지가 0일 때, 아닐 때를 구분 지었다.

0이 아닐 때 개수를 몫+1로 두었다. 만약 10초이고 작업시간이 9초라면 10초 때에는 작업을 두 번 하기 때문이다.

만약 개수가 n이상이라면 for문을 멈추고 범위를 재조정한다.

 

        if (cnt < n && cnt + div.size() >= n) {
            return div[n - cnt - 1] + 1;
        }
        else if (cnt >= n) {
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }

 

만약 n = 4, mid=3, cnt = 4, 코어는 {5,5,5,5}라고 가정하자,

그러면 우리는 cnt가 4일 때가 아닌, cnt가 4 미만일 때를 찾아야 한다. mid를 더 낮춰야 한다는 뜻이다.

cnt가 n보다 작고, 작업을 막 시작하려는 코어의 수인 div의 수와 cnt를 더한 값이 n이상이라면 정답을 찾은 것이다.

div에는 idx+1이 아닌 idx값을 넣었으니 div [n - cnt - 1]에 +1을 한다.

 

답을 찾지 못했다면 cnt가 n이상일 때는 시간을 줄이고, 반대의 경우는 시간을 늘린다.

 

 

코드

#include <string>
#include <vector>
#include <algorithm>
#define MAX 2147483646
using namespace std;

int solution(int n, vector<int> cores) {
    int answer(0), idx(0), left(1), right(MAX), mid(0), cnt(0);
    vector<int>div;
    
    if (n <= cores.size())
        return n;

    while (left <= right) {
        mid = (left + right) / 2;
        cnt = 0;
        div = vector<int>();
        for (idx = 0; idx < cores.size(); ++idx) {
            if (mid % cores[idx] != 0)
                cnt += (mid / cores[idx] + 1);
            else {
                div.push_back(idx);
                cnt += (mid / cores[idx]);
            }
            if (cnt >= n) break;
        }
        
        if (cnt < n && cnt + div.size() >= n) {
            return div[n - cnt - 1] + 1;
        }
        else if (cnt >= n) {
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    }
}