해설
문제를 보자마자 오 이거 우선순위 큐 쓰면 되겠다 하고 빠르게 풀었다.
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;
}
'ㄴ 알고리즘 > 프로그래머스풀이' 카테고리의 다른 글
[프로그래머스 lv3] 아이템 줍기 풀이 (0) | 2022.09.21 |
---|---|
[프로그래머스 lv3] 매칭 점수 풀이 (0) | 2022.09.20 |
[프로그래머스 lv3] 모두 0으로 만들기 풀이 (0) | 2022.09.20 |
[프로그래머스 lv3] 블록 이동하기 풀이 (0) | 2022.09.19 |
[프로그래머스 lv3] 광고 삽입 풀이 (0) | 2022.09.19 |
댓글