문제 설명

처리해야 할 동일한 작업이 n 개가 있고, 이를 처리하기 위한 CPU가 있습니다.

이 CPU는 다음과 같은 특징이 있습니다.

• CPU에는 여러 개의 코어가 있고, 코어별로 한 작업을 처리하는 시간이 다릅니다.
• 한 코어에서 작업이 끝나면 작업이 없는 코어가 바로 다음 작업을 수행합니다.
• 2개 이상의 코어가 남을 경우 앞의 코어부터 작업을 처리 합니다.

처리해야 될 작업의 개수 n과, 각 코어의 처리시간이 담긴 배열 cores 가 매개변수로 주어질 때, 마지막 작업을 처리하는 코어의 번호를 return 하는 solution 함수를 완성해주세요.

제한 사항

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

입출력 예

n	cores	result
6	[1,2,3]	2

입출력 예 설명

입출력 예 #1
처음 3개의 작업은 각각 1,2,3번에 들어가고, 1시간 뒤 1번 코어에 4번째 작업,다시 1시간 뒤 1,2번 코어에 5,6번째 작업이 들어가므로 2를 반환해주면 됩니다.

접근 방법

이번 문제는 처음에 봤을 때에는 큐를 사용해야 한다고 생각하였다. 문제에서 주어진대로 구현을 하려고 생각했기 때문이었다. 큐로 구현을 하던 중 큐에 담지 않아도 구현할 수 있겠다는 생각이 들었고, 큐를 사용하지 않고 간단하게 구현하였다.

def solution(n, cores):
    answer = 0
    time=0
    tmp=0
    cur=1+len(cores)
    while True:
        if cur>n:
            break
        time+=1
        for i in range(len(cores)):
            if cur>n:
                answer=tmp+1
                break
            if time%cores[i]==0:
                cur+=1
                tmp=i
    return answer

이 방식은 정확성 테스트는 모두 통과했지만, 효율성 테스트를 모두 통과하지 못하였다. 그러다가 이분 탐색에 대해 생각하게 되었고, 이분 탐색을 활용하면 시간을 줄일 수 있을 것이라 생각했다. 여기서 left, right, mid는 실행 시간에 해당하게 된다. 이 문제를 그림으로 생각해보니, 시간 당 수행하게 되는 프로세스의 갯수는 시간의 약수인 작업시간을 갖는 cpu들의 합이라는 것을 알 수 있었다. 이를 이용하여 mid시간까지 수행한 프로세스의 갯수가 n보다 크거나 같은 지점을 찾고, 남은 만큼을 순회하며 마지막 cpu를 찾았다.

solution.py

def solution(n, cores):
    if n<=len(cores):
        return n
    n-=len(cores)
    left, right=1, max(cores)*n
    while left<right:
        mid=(left+right)//2
        proc=0
        for core in cores:
            proc+=mid//core
        if proc>=n:
            right=mid
        else:
            left=mid+1
    for core in cores:
        n-=(right-1)//core
    for i in range(len(cores)):
        if right%cores[i]==0:
            n-=1
            if n==0:
                return i+1