문제

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

---

입력

• 처리해야 될 작업의 개수 n
• 각 코어의 처리시간이 담긴 배열 cores

---

출력

마지막 작업을 처리하는 코어의 번호

---

풀이

제한조건

• 코어의 수는 10,000 이하 2이상 입니다.
• 코어당 작업을 처리하는 시간은 10,000이하 입니다.
• 처리해야 하는 일의 개수는 50,000개를 넘기지 않습니다

접근방법

우선 순위 큐 -> X
우선 순위 큐를 이용하여, 1번째 작업부터 N번째 작업까지 순차적으로 할당하며 진행해 보았다.
N번째 작업이 완료될때까지, 각 작업을 순차적으로 모두 진행하며 우선 순위 큐에서 정렬을 한다.

코어의 수와 작업의 개수가 크지 않아서 통과할 것이라고 생각하였으나, 효율성 체크에서 실패한다.

실패코드

import java.util.*;

class Core implements Comparable<Core>{
	int coreNum; // 코어의 번호
	int nextRunTime; // 다음 코어가 동작할 수 있는 시간

	Core(int a, int c){
		coreNum = a;
		nextRunTime = c;
	}

	public int compareTo(Core o){
		if(this.nextRunTime == o.nextRunTime)
			return this.coreNum - o.coreNum;
		return this.nextRunTime - o.nextRunTime;
	}
}
class Solution {
	public int solution(int n, int[] cores) {
		int answer = 0;

		PriorityQueue<Core> pq = new PriorityQueue();
		int len = cores.length;
		int last = 0;
		for(int i = 0 ; i < len && i < n; ++i){
			pq.add(new Core(i, cores[i]));
			last = i;
		}

		int start = n - len;
		if(start >= 0){
			for(int i = len; i < n; ++i){
				Core cur = pq.poll();
				cur.nextRunTime += cores[cur.coreNum];
				pq.add(cur);
				last = cur.coreNum;
			}
		}

		return last + 1;
	}
}

파라메트릭 서치 -> O
(parametric Search를 모른다면, https://velog.io/@hyeokkr/%EC%9D%B4%EB%B6%84%ED%83%90%EC%83%89)

위에서 구현한것을 조금 더 최적화 해보자.
우선 순위큐를 사용한 방법에서는 각 작업 마다 현재 가능한 코어의 시간을 정리하며 계속 순회했다.

파라메트릭 서치를 이용하여, N개가 완료되는 시간을 우선 찾아보자.

해당 시간을 찾았다면, 첫 번째 코어부터 시작할 수 있는지 확인한다.
( 여러 코어가 작업을 할 수 있다면, 문제 조건에 의해서 앞 번호의 코어에 먼저 할당됨)

주의할점은 코어의 번호는 1번부터, 배열의 인덱스는 0부터..
즉, 정리하자면 아래와 같다.

1. N개의 작업이 완료되는 최소시간 구하기.
2. 최소시간 - 1 시점의 완료된 작업 수 구하기.
3. 첫번째 코어부터 최소 시간에 작업을 하나씩 할당.
4. 3과정에서 N번째 작업이 할당될 때 기록.

---

코드

import java.util.*;

class Solution {
    public int solution(int n, int[] cores) {
        int len = cores.length;

        if (n <= len) 
            return n;

        // 우선 N 개의 작업이 완료되는 최소 시간을 구한다.
        int minCore = Arrays.stream(cores).min().getAsInt();
        int left = 1;
        int right = n * minCore;

        while (left <= right) {
            int midTime = (left + right) / 2;
            int completeProcess = len;

            // 완료된 작업의 수 체크
            for (int core : cores) {
                completeProcess += midTime / core;
            }

            if (completeProcess < n) {
                left = midTime + 1;
            } else {
                right = midTime - 1;
            }
        }
        // N개의 작업이 완료되는 최소 시간을 계산 완료
        // System.out.println(left);
        
        int done = len;
        for (int core : cores) {
            done += (left - 1) / core;
        }

        // 가장 빠른 코어부터, left 시간에 마지막 작업이 시작하는지 확인.
        int last = 0;
        for (int i = 0; i < len; ++i) {
            if (left % cores[i] == 0) {
                done++;
            }
            if (done == n) {
                last = i;
                break;
            }
        }

        return last + 1;
    }
}