Lv4. 선입 선출 스케줄링

# 문제 설명

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

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

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

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

# 제한 사항

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

# 입출력 예

입출력 예 설명

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

문제 해결 시 고려사항

• 마지막 작업이 작업되는 시간을 찾아내는 이분탐색!

본 문제는 처리시간이 각각 주어진 cores를 통해 n개의 작업을 실시했을 때, 마지막 작업이 몇 번 core에서 처리되는지를 알아내는 문제이다.

따라서 본 문제를 해결하기 위해서는 마지막 작업이 어느 시점에 처리되는지 알아내는 것이 핵심인 것이다. 필자는 그 시점을 알아내기 위하여 이분탐색을 적용하여 문제를 해결하였다. 하지만 이분탐색을 효율적으로 구성하기 위해 low와 high를 최적으로 선정하는 것 또한 중요하다. 필자는 아래와 같이 low와 high를 설정하였다.

 low = n // len(cores) * min(cores)
 high = n * min(cores)
 mid = (low+high) // 2

이 후, 아래와 같은 이분탐색을 통하여 마지막 작업이 작업되는 시간을 찾고 작업을 진행하는 코어의 번호 또한 알아낼 수 있었다.

 while low < high:
         cnt = 0
         avail = 0
         for core in cores:
             cnt += mid//core + 1
             # mid 시간 도달 직전까지 해당 코어의 수행 작업 수 검사
             if mid % core == 0:
                 avail += 1
                 cnt -=1
         # 총 수행 작업이 n개 이상이면 high를 mid로 조정
         if cnt >= n:
             high = mid
         # 총 수행 작업과 삽입 가능 코어의 개수가 n보다 작으면 low를 mid+1로 조정
         elif cnt + avail < n:
             low = mid +1
         # 그렇지 않은 경우(조건에 맞는 mid 시간 발견 시)에는
         else:
             # 각 코어 별 수행 작업수 계산
             for i in range(len(cores)):
                 if mid % cores[i] == 0:
                     cnt+=1
                 # cnt와 n이 일치하면 해당 코어의 번호 리턴
                 if cnt == n:
                     return i+1
         # mid 재조정 후 반복문을 다시 돎
         mid = (low+high) // 2

전체 코드

def solution(n, cores):
    answer = 0
    # 마지막 작업이 큐에 들어가는 시간을 찾아내는 이분탐색 실시
    low = n // len(cores) * min(cores)
    high = n * min(cores)
    mid = (low+high) // 2
    while low < high:
        cnt = 0
        avail = 0
        for core in cores:
            cnt += mid//core + 1
            # mid 시간 도달 직전까지 해당 코어의 수행 작업 수 검사
            if mid % core == 0:
                avail += 1
                cnt -=1
        # 총 수행 작업이 n개 이상이면 high를 mid로 조정
        if cnt >= n:
            high = mid
        # 총 수행 작업과 삽입 가능 코어의 개수가 n보다 작으면 low를 mid+1로 조정
        elif cnt + avail < n:
            low = mid +1
        # 그렇지 않은 경우(조건에 맞는 mid 시간 발견 시)에는
        else:
            # 각 코어 별 수행 작업수 계산
            for i in range(len(cores)):
                if mid % cores[i] == 0:
                    cnt+=1
                # cnt와 n이 일치하면 해당 코어의 번호 리턴
                if cnt == n:
                    return i+1
        # mid 재조정 후 반복문을 다시 돎
        mid = (low+high) // 2
    return answer