[프로그래머스] 선입 선출 스케줄링

문제 요약

처리 시간이 서로 다른 여러 CPU 코어에 작업을 순서대로 배정한다.

• 시작 시각에는 모든 코어가 비어 있으므로, 앞 번호 코어부터 작업을 하나씩 받는다.
• 어떤 코어의 작업이 끝나면 즉시 다음 작업을 받는다.
• 같은 시각에 여러 코어가 비면 번호가 작은 코어부터 작업을 받는다.

n번째, 즉 마지막 작업을 처리하는 코어 번호를 반환한다.

핵심 아이디어

시간 time이 주어졌을 때, 그 시각까지 배정된 작업 수를 계산할 수 있다.

처음 시각에 배정되는 작업 수: 코어 개수
이후 각 코어가 처리한 작업 수: time // 코어 처리 시간

따라서 전체 작업 수는 다음과 같다.

len(cores) + sum(time // core for core in cores)

시간이 증가할수록 이 값은 줄어들지 않는다. 그러므로 n번째 작업이 배정되는 최소 시각을 이분 탐색으로 찾을 수 있다.

마지막 코어 찾기

최소 시각을 time이라고 하자.

time - 1까지 배정된 작업 수를 구하면, time에 동시에 비는 코어들 중 몇 번째 코어가 n번째 작업을 받는지 알 수 있다.

remaining = n - (time - 1초까지 배정된 작업 수)

앞 번호 코어부터 확인하면서 time % core == 0인 코어를 만날 때마다 remaining을 하나씩 줄인다. 값이 0이 되는 코어가 답이다.

풀이 과정

1. 작업 수가 코어 수 이하라면 시작 시각에 배정되므로 답은 n번 코어다.
2. 이분 탐색으로 n번째 작업이 배정되는 최소 시각을 찾는다.
3. 그 직전 시각까지 배정된 작업 수를 구한다.
4. 최소 시각에 비는 코어를 번호순으로 확인해 마지막 작업의 코어를 찾는다.

Python 코드

def solution(n, cores):
    core_count = len(cores)

    # 시작 시각에 앞 번호 코어부터 하나씩 작업을 받는다.
    if n <= core_count:
        return n

    def assigned_work_count(time):
        return core_count + sum(time // core for core in cores)

    left = 0
    right = max(cores) * (n - core_count)

    # n번째 작업이 배정되는 최소 시각을 찾는다.
    while left < right:
        mid = (left + right) // 2

        if assigned_work_count(mid) >= n:
            right = mid
        else:
            left = mid + 1

    time = left
    assigned_before = assigned_work_count(time - 1)
    remaining = n - assigned_before

    # 같은 시각에 비는 코어는 번호순으로 다음 작업을 받는다.
    for index, core in enumerate(cores, start=1):
        if time % core == 0:
            remaining -= 1

            if remaining == 0:
                return index

예시

n = 6, cores = [1, 2, 3]인 경우를 보자.

시각	비는 코어	배정되는 작업
0	1, 2, 3	1, 2, 3
1	1	4
2	1, 2	5, 6

6번째 작업은 시각 2에 비는 코어 중 두 번째인 2번 코어에 배정되므로 답은 2다.

시간 복잡도

C를 코어 수, T를 탐색 시간의 최댓값이라고 하자.

• 작업 수를 계산하는 데 O(C)

• 이분 탐색은 O(log T)

• 마지막 코어를 찾는 데 O(C)

• 시간 복잡도: O(C log T)

• 공간 복잡도: O(1)

정리

작업 하나씩을 직접 시뮬레이션할 필요가 없다. n번째 작업이 배정되는 시각을 먼저 찾고, 그 시각에 비는 코어를 번호순으로 세면 마지막 작업을 처리하는 코어를 구할 수 있다.