Programmers / 선입선출스케줄링 / Python 파이썬

 

*문제 출처는 프로그래머스에 있습니다.

문제 제목: 선입선출 스케줄링 (3단계) - 이분탐색

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/12920

프로그래머스

문제 설명

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

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

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

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

제한 사항

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

---

입출력 예ncoresresult

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
    if n <= len(cores): # n이 코어의 길이보다 작으면 n을 리턴
        return n
    n -= len(cores)
    start = 1
    end = max(cores) * n # n번째 작업량이끝나는 시간보다 큰 수 중 가장 작은 시간 구하기을 구하기
    
    while start < end:
        mid = (start + end) // 2
        jobs = 0
        for c in cores:
            jobs += mid//c # mid 시간 내에 한 코어당 끝낼 수 있는 작업의 총 갯수
            
        if jobs >= n:
            end = mid
        else:
            start = mid + 1
        
    for c in cores:
        n -= (end-1) // c 
        
    for i in range(len(cores)):
        if end % cores[i] == 0:
            n -= 1
            if n == 0:
                return i + 1

참고 사이트

https://dev-note-97.tistory.com/173

 

---

※ 알아야 할 것

- left = 1, right = max(cores) * n 에서 시작해서, mid = left + right // 2 로 계산해나가며, 만약 mid값의 총 작업수(capacity)가 타겟 작업수인 n 보다 크거나 같은 지점을 찾는 것이 목표

-  'n보다 큰 값 중 가장 작은 값'을 구하는 것이기 때문에, 이분탐색에서도 lower bound 알고리즘

- 작업량의 시간에 대해 이분탐색을 실시함