[프로그래머스 lv3] 선입 선출 스케줄링 풀이

해설

 

문제를 보자마자 오 이거 우선순위 큐 쓰면 되겠다 하고 빠르게 풀었다.

n개의 작업을 처리할 때마다 가장 작업을 빨리 시작할 수 있는 코어를 찾고, 해당 코어의 다음 시작 지점을 수정하는 방법이다.

시간복잡도도 O(NlogN)으로 여유롭다고 생각했는데... 이런! 효율성 통과가 안된다.

 

int solution(int n, vector<int> cores) {
    
    priority_queue<ii, vector<ii>, greater<ii>> pq;
    
    for (int i=0; i<(int)cores.size(); i++)
        pq.push({0, i});
    
    for (int i=1; i<=n; i++) {
        ii cur = pq.top();
        if (i == n) return cur.Y+1;
        pq.pop();
        cur.X += cores[cur.Y];
        pq.push(cur);
    }
    return -1;
}

 

 

다른 방법이 있을까 싶어서 시간대별 작업 현황을 그림으로 그려보았다.

그랬더니, 일단 이분탐색을 이용하면 n개의 작업을 모두 처리할 수 있는 최소 시간을 구할 수 있겠다는 생각이 들었다.

 

1) 시간의 탐색 범위 시작을 first, 탐색 범위 끝을 last으로 지정해 놓고 탐색 범위를 반으로 줄이면서 해당 시간 동안 n개의 작업을 모두 처리할 수 있는지 확인한다. 만약 mid 시간에 n개를 모두 처리할 수 있다면 last = mid-1로,  n개를 모두 처리할 수 없다면 first = mid+1로 조정한다.

 

2) mid 시간 내에 n개를 모두 처리할 수 있는지 확인하려면, cores를 모두 순회하면서 t/cores[i]+1 의 합이 n 이상인지 확인하면 된다. 예를 들어, 작업 처리시간이 2인 코어에서 t = 3 동안 처리할 수 있는 작업 양은 [0초 시작, 2초 시작] 이렇게 두 개이다. t/2가 아니라, t/2+1로 계산해주어야 해당 시각을 시작점으로 하는 작업량까지 모두 포함하여 계산할 수 있다.

 

3)  n개의 작업을 모두 처리할 수 있는 최소 시각을 t라 하자. 그 이야기인 즉슨, t-1시각까지는 n개가 안되었는데, 1시간이 지나고 t가 되었을 때 몇몇의 코어에서 새로운 작업이 시작되어 작업량이 늘고 n개가 되었다는 말이다.

 

따라서, t-1 시각까지의 작업량을 구해놓은 뒤(cnt) 코어를 돌면서 t시각에 추가된 n번째 작업을 찾으면 된다. t%cores[i]가 0일 때 t 시각에서 새로운 작업이 추가된다. t%cores[i]가 0이 될 때 cnt에 1을 추가하고 cnt가 n이 되면 해당 코어의 번호를 리턴하자.

 

4) 코어의 번호는 1-index 기반임에 주의하자.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using ll = long long;

#define X first
#define Y second

int sz, nwork, mx;

bool check(ll t, const vector<int>& cores) {
    
    ll cnt = sz;
    for (int i=0; i<sz; i++)
        cnt += t/cores[i];
    return cnt >= nwork;
}

int binarySearch(const vector<int>& cores) {
    
    int first = 0;
    int last = mx*(nwork/sz);
    int ret = last;
    
    while (first <= last) {
        ll mid = (first+last)/2;
        if (check(mid, cores)) {
            ret = mid;
            last = mid-1;
        }
        else first = mid+1;
    }
    
    return ret;
}

int solution(int n, vector<int> cores) {
    
    nwork = n;
    sz = cores.size();
    for (int i=0; i<sz; i++) mx = max(cores[i], mx);
    
    //t: 작업을 n개 이상 수행하기 위한 최소 시각
    int t = binarySearch(cores);
    if (t == 0) return n;
    
    //cnt: t-1시간까지의 작업량
    ll cnt = sz;
    for (int i=0; i<sz; i++) 
        cnt += (t-1)/cores[i];
    
    //시각 t에 작업이 추가될 때 n번째 작업이 추가되는 코어 번호 리턴
    for (int i=0; i<sz; i++) {
        if (t%cores[i] != 0) continue;
        if (++cnt == n) return i+1;
    }
    
    return -1;
}