문제출처: https://programmers.co.kr/learn/courses/30/lessons/12920
문제 설명
처리해야 할 동일한 작업이 n 개가 있고, 이를 처리하기 위한 CPU가 있습니다.
이 CPU는 다음과 같은 특징이 있습니다.
CPU에는 여러 개의 코어가 있고, 코어별로 한 작업을 처리하는 시간이 다릅니다.
한 코어에서 작업이 끝나면 작업이 없는 코어가 바로 다음 작업을 수행합니다.
2개 이상의 코어가 남을 경우 앞의 코어부터 작업을 처리 합니다.
처리해야 될 작업의 개수 n과, 각 코어의 처리시간이 담긴 배열 cores 가 매개변수로 주어질 때, 마지막 작업을 처리하는 코어의 번호를 return 하는 solution 함수를 완성해주세요.
제한 사항
- 코어의 수는 10,000 이하 2이상 입니다.
- 코어당 작업을 처리하는 시간은 10,000이하 입니다.
- 처리해야 하는 일의 개수는 50,000개를 넘기지 않습니다.
PriorityQueue를 사용해서 푼 코드 (효율성 실패)
class Solution {
public int solution(int n, int[] cores) {
int answer = 0;
if (n < cores.length) return n;
PriorityQueue<Core> pq = new PriorityQueue<Core>();
for (int i = 0; i < cores.length; i++) {
pq.offer(new Core(i + 1, cores[i], cores[i]));
}
int timeFlow = 0;
for (int i = cores.length; i < n; i++) {
Core c = pq.peek();
if (i == n - 1) answer = c.index;
if (c.worktime > timeFlow) {
timeFlow += c.worktime;
}
pq.poll();
c.worktime += c.timeTotal;
pq.offer(c);
}
return answer;
}
class Core implements Comparable<Core>{
int index;
int timeTotal;
int worktime;
public Core(int index, int timeTotal, int worktime) {
this.index = index;
this.timeTotal = timeTotal;
this.worktime = worktime;
}
@Override
public int compareTo(Core c) {
if (this.worktime > c.worktime) {
return 1;
}
else if (this.worktime < c.worktime) {
return -1;
}
else {
if (this.index > c.index) {
return 1;
}
else if (this.index < c.index) {
return -1;
}
else {
return 0;
}
}
}
}
}처음에는 PriorityQueue를 사용하여 풀려고 했다가 효율성 테스트에서 계속 실패했다. 결국 어떤분이 남긴 댓글을 보니 Parametric Search를 사용하면 풀린다고 해서 찾아봤다.
대충 찾아보니 이진탐색과 비슷한데 정확한 값을 찾는게 아닌 가능한 답의 특정 Range를 찾는 알고리즘인 듯 하다.
근데 아무리 고민해봐도 어떤 값을 매개변수로 Parametric Search를 사용해야할지 감이 오질 않아서 결국 mstst33님의 답을 참고했다. (link: https://www.mstst33.com/programmers-first-in-first-out-scheduling/162/)
답을 봤는데도 이해하는데 한참 걸렸다...
Parametric Search를 사용해서 푼 코드 (효율성 성공)
class Solution {
public int solution(int n, int[] cores) {
int answer = 0;
int coreMin = cores[0];
int coreMax = cores[0];
if (n <= cores.length) return n;
for (int i = 0; i < cores.length; i++) {
if (coreMin > cores[i]) coreMin = cores[i];
if (coreMax < cores[i]) coreMax = cores[i];
}
int mintime = (coreMin * n) / cores.length - coreMin;
int maxtime = (coreMax * n) / cores.length - coreMax;
int midtime;
while (mintime <= maxtime) {
midtime = (mintime + maxtime) / 2;
int workDone = cores.length; // 작업 시작부터 코어수만큼 작업이 할당된다
int currentWork = 0; // 현재시간에 작업을 할당 받는 core 수
for (int i : cores) {
workDone += (midtime / i); // 현재시간 (midtime) 기준 해당 core가 처리한 작업수
if (midtime % i == 0) currentWork++;
}
if (n > workDone) { // 현재까지 처리한 작업수 + 처리되고 있는 작업수가 n보다 적으면 mintime 을 midtime 으로 끌어올린다
mintime = midtime + 1;
}
// 현재까지 처리한 작업수가 n 보다 크거나 같으면 maxtime을 midtime으로 끌어내린다
else if (n <= workDone - currentWork) {
maxtime = midtime - 1;
}
// workDone - currentWork < n <= workDone
// 현재까지 처리한 작업수 < n <= 현재까지 처리한 작업수 + 처리되고 있는 작업수
else {
int count = 0;
// 현재 처리될 작업 중 몇번째 작업에서 마지막 작업을 처리하는 구한다
for(int i = 0; i < cores.length; ++i){
if((midtime % cores[i]) == 0) count++;
if(count == n - (workDone - currentWork)) return (i + 1);
}
}
}
return answer;
}
}설명하자면 우선 매개변수로 사용해야할 값은 '총 작업시간'이다. 좀 더 정확히 말하면 n번째(마지막) 작업이 코어에 할당되는데 걸리는 시간이다. 그렇다면 최소값과 최대값은 어떻게 구할수있을까. 모든코어의 작업시간이 같다고 가정하면 된다. cpu가 코어들 중 가장 빠른 작업 속도를 가진 코어로만 이루어졌다고 가정하면 최소값을 구할 수 있고, 그 반대로 가장 느린 작업속도를 가진 코어로만 이루어졌다고 가정하면 최대값을 구할수 있다. 따라서 "최소값 = ((최소작업시간 * 처리해야하는 작업수) / 코어의수) - 최소작업시간" 이 된다. 마지막에 최소작업시간을 빼는 이유는 시작할때부터 모든코어에 작업이 할당되고 모든 코어는 작업을 완료하는데 최소작업시간이 걸린다고 가정했기 때문이다.
이제 최소값과 최대값을 이용하여 Parametric Search를 한다. 이 탐색을 통해 n번째 작업이 할당된 시간을 찾아야 하는데 그러기 위해선 특정시간까지 완료된 작업수와 그시간에 할당된 작업수가 필요하다. 예를 들어 7시에 n번째 작업이 처리되려면 (7시까지 처리된 작업수 ~ 7시까지 처리된 작업수 + 7시에 작업 가능한 코어수) 범위 안에 n이 있어야 한다. 코드에서 'workDone'은 '처리된 작업수 + 작업 가능한 코어수' 이고 'currentWork'는 현재 작업 가능한 코어의 수를 뜻한다.
이 방법을 사용하면 효율성테스트까지 모두 통과 할수 있다.
