프로그래머스 [Lv. 3] 선입 선출 스케줄링 {언어 : Python} [다시 풀어 보기]

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12920?language=python3#

프로그래머스

정답 코드

def solution(n, cores):
    answer = 0
    lenC = len(cores)
    
    # 코어의 개수보다 작업의 수가 적거나 같으면 바로 답을 구할 수 있음
    if n <= lenC:
        answer = n
    else:
        n -= lenC  # 초기 작업 수에서 코어 수를 뺌
        minTime = min(cores)
        maxTime = max(cores) * n
        
        # 이진 탐색을 이용하여 작업을 완료하는 데 필요한 최소 시간을 찾음
        while minTime < maxTime:
            midTime = (minTime + maxTime) // 2
            throughput = 0
            for core in cores:
                throughput += midTime // core
            if throughput >= n:
                maxTime = midTime
            else:
                minTime = midTime + 1
        
        # 찾은 최소 시간에서 남은 작업 수를 계산
        for core in cores:
            n -= (maxTime - 1) // core
        
        # 마지막 작업을 처리하는 코어를 찾음
        for i in range(lenC):
            if maxTime % cores[i] == 0:
                n -= 1
                if n == 0:
                    answer = i + 1
                    break
    
    return answer

풀이 방법

 

1. 먼저, 코어의 개수(lenC)와 처리해야 할 작업의 수(n)를 비교하여, 만약 n이 코어의 개수보다 작거나 같다면 바로 답을 구할 수 있다. 이 경우 n번째 코어가 마지막 작업을 처리하게 된다.
2. 그렇지 않은 경우, 이진 탐색을 사용하여 작업을 완료하는 데 필요한 최소 시간을 찾는다.
3. 최소 시간을 찾은 후, 각 코어가 maxTime에서 작업을 완료할 때까지의 남은 작업 수를 계산한다.
4. 마지막으로, 어느 코어가 maxTime에 작업을 처리하게 되는지 찾아 해당 코어의 인덱스를 반환한다.

 

느낀점

• heap으로 풀어봤는데 효율성에서 15/30 점을 받았다.
• 이게 이분 탐색으로 푸는 문제라니... 다시 풀어서 외우는 것이 좋겠다.