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

문제주소 :programmers.co.kr/learn/courses/30/lessons/12920

코딩테스트 연습 - 선입 선출 스케줄링

---

<문제 설명>

문제 설명

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

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

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

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

제한 사항

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

---

입출력 예

n                                                cores                                        result

6

[1,2,3]

2

입출력 예 설명

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

 

<풀이법>

▒ 한줄 개념: 이분 탐색 ▒ 

처음에는 코어의 수와 처리할 일의 갯수의 사이즈가 크지 않아 직접 반복문을 돌려서 시도했는데, 실패하였습니다..

역시 Level 4... 따라서 효율성을 생각해보게 되었고, Level 3의 입국 심사 문제와 비슷하다는 느낌이 들어서 이분탐색으로 시도하여 통과하였습니다. 어떤 분들은 paraemtric search? 라는 방법을 사용하셨다는데.. 그게 더 효율적인 방법일 수도 있을 것 같습니다.

>>이분탐색 Level 3. 입국 심사 문제 보러가기<<

 

풀이 방식은 다음과 같습니다.

 

#1.

우선 만약 n값이 cores의 길이보다 작을 경우, n값이 곧 정답입니다. 시작과 동시에 모든 cpu에 차례로 작업이 하나씩 시작되므로, 앞에서부터 n번째 cpu가 마지막 작업을 처리하게 될 cpu입니다.

ex) n = 4, cores = [1,2,3,4,5,6,7] -> answer = 4

 

 

#2.

이분탐색을 진행하는데, left, right, mid 값은 시간값이 될 것이며, n과 비교할 것은 capacity로, n-1 시간동안 처리된 작업의 양이 됩니다. n = 10, cores = [1,2,3,4] 의 예시가 있을 때,

시간 진행에 따른 총 작업 수

다음과 같은 규칙으로 매 시간마다 작업이 진행됩니다. 

1h에는 1의 약수인 1값을 갖는 cpu만이 작업이 추가되고,

2h에는 2의 약수인 1,2 값을 갖는 cpu가 작업에 추가되고,

3h에는 3의 약수인 1,3 값을 갖는 cpu가 작업에 추가되고,

4h에는 4의 약수인 1,2,4 값을 갖는 cpu가 작업에 추가되고,

5h에는 5의 약수인 1 값을 갖는 cpu가 작업에 추가됩니다.

따라서 어떤 시간 h에 대해, 시작(0h)를 제외하고 진행된 총 작업 수는 매 시간(h)에 대해, 새로 추가되는 작업 수는 sum(h의 약수인 작업시간을 갖는 cpu들) 이라는 것입니다.

이를 이용해 어떤 시간 h가 있을 때, 진행된 총 작업 수를 구할 수 있습니다. 

 

left,right 값을 이용해서 mid의 값을 얻을 것인데, 위에서 말했듯 이 값들은 시간(h) 값입니다. 즉, left = 1, right = max(cores) * n 에서 시작해서, mid = left + right // 2 로 계산해나가며, 만약 mid값의 총 작업수(capacity)가 타겟 작업수인 n 보다 크거나 같은 지점을 찾는 것이 목표입니다. 여기서 배열내에 있는 값이 아닌 'n보다 큰 값 중 가장 작은 값'을 구하는 것이기 때문에, 이분탐색에서도 lower bound 알고리즘이라고 볼 수 있습니다.

(왜 n = capacity가 아닌 n보다 큰 것중에서 가장 작은 capacity를 탐색하느냐 하면, 문제의 정답이 시간(h)을 구하는 것이 아닌 몇 번째 cpu인지를 구하는 것이기 때문입니다.)

 

#3.

반복문을 통해 몇 번째 cpu가 마지막이 될 것인지 확인

찾아낸 (h-1) 까지의 총 작업수를 n에서 뺍니다. 그러면 남아있는 작업 수는 전부 현재 시간(h) 안에서만 이루어졌다는 것이 됩니다. 

다시 한번 n = 10, cores = [1,2,3,4] 의 예시에서, 정답은 4h의 1번 cpu입니다.

 

3h까지의 작업 수가 9이므로, n-1 = 1, 즉 한 개의 작업만 더 실행되면 됩니다. 따라서, 4h에서 진행 가능한 cpu 중 가장 앞에 있는 cpu인 1이 정답이 되는 것입니다.

다시 설명해서, h - 1시간까지의 총 작업량을 구한 뒤에, h 시간의 cpu를 하나씩 진행가능한 상태인지 count하며 n의 값이 채워지면, 그것이 정답이 되는 것입니다. 

 

위와 같은 방식으로 만약 n = 12라면, 3h까지 9개의 작업을 진행하고 나서 3개의 작업이 더 필요하니, 4h의 작업가능한 세번째 cpu, 4번 cpu가 정답이 되는 것입니다.

 

 

<코드(Python)>

def solution(n, cores):

    if n <= len(cores):
        return n
    else:
        n -= len(cores)
        left = 1
        right = max(cores) * n

        while left < right:
            mid = (left + right) // 2
            capacity = 0
            for c in cores:
                capacity += mid // c
            if capacity >= n:
                right = mid
            else:
                left = mid + 1

        for c in cores:
            n -= (right-1) // c

        for i in range(len(cores)):
            if right % cores[i] == 0:
                n -= 1
                if n == 0:
                    return i + 1

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest