[프로그래머스] 선입선출

[문제 설명]

주어진 작업을 처리하기 위한 여러 개의 코어가 있는 CPU가 있습니다. 각 코어는 작업을 처리하는 시간이 다르고, 작업이 끝나면 작업이 없는 코어가 다음 작업을 수행합니다. 처리해야 할 작업의 개수와 각 코어의 처리 시간이 주어질 때, 마지막 작업을 처리하는 코어의 번호를 반환하는 함수를 작성해야 합니다.

 

[해결 방법]

 우선 이 문제를 풀기 위해선 모든 작업들이 코어에 할당되는 최소 시간을 찾아야 합니다. 이를 빠르게 찾기 위해 이분탐색을 사용했습니다. 

구체적인 해결 방법은 아래와 같습니다.

1. 이분 탐색을 통해 최소 시간을 구합니다.
2. (최소 시간  - 1)을 하여 해당 시간에 코어가 처리하고 있는 작업의 수를 파악합니다.
3.  (코어 시간 % 최소시간 == 0)이면 해당 시간에 코어에 작업을 할당할 수 있다는 의미이니 마지막 작업이 입력되는 코어의 숫자를 리턴하면 됩니다.

최종적인 시간 복잡도는 O(log(max(cores)) * n)입니다.

 

 

[해결 과정에서 발생한 문제와 해결방법] 

• 문제를 보자마자 이분 탐색은 생각했지만, 제일 마지막에 할당된 코어를 찾는 것이 어렵다고 판단했습니다. 따라서 작업의 수(n)이 작은것을 파악하고,  작업의 할당 순서를 이용해 문제를 풀이할려고 했습니다.  하지만 가장 빨리 끝나는 코어의 시간을 찾기 위해서 반복문이 들어가면서 최종 시간 복잡도는 O(n^(len(cores))가 되어 시간초과가 발생했습니다.  

[잘못된 풀이] 

def solution(n, cores):
    answer = 0
    time = 0

    is_run_cores = [0] * len(cores)

    #남은 일의 개수
    while 0 < n:
        min_time = 10001   # 끝나는 시간 중 최소값을 찾기 위해 큰 값으로 초기화
        min_idx = 0        # 가장 빨리 끝나는 코어의 인덱스
        for idx in range(len(is_run_cores)):
            if is_run_cores[idx] < min_time:
                min_time = is_run_cores[idx]
                min_idx = idx
        is_run_cores[min_idx] += cores[min_idx]  # 작업을 처리하는 코어에 대해 처리 시간을 더해줍니다.
        n -= 1
        answer = min_idx + 1  # 마지막으로 처리한 코어의 인덱스를 저장합니다.

    return answer

[정답 코드]

def solution(n, cores):
    n -= len(cores)
    left = -1
    right = max(cores) * n 
    
    while left + 1 < right:
        mid = (left + right) // 2

        done = 0
        for core in cores:
            done += mid // core

        if done < n:
            left = mid
        else: 
            right = mid

    done = 0
    
    for core in cores:
        done += (right- 1) // core

    for i, core in enumerate(cores):
        if right % core == 0: 
            done += 1
            if done == n:  # 마지막 작업이 처리되면 해당 코어의 번호를 반환합니다.
                return i + 1
    return -1

if __name__ == "__main__":
    n = 6
    cores = [1,2,3]

    print(solution(n, cores))