[Python] 파이썬 프로그래머스 선입 선출 스케줄링

https://school.programmers.co.kr/learn/courses/30/lessons/12920

프로그래머스

---

나의 풀이

• 처리해야 할 동일한 작업이 n개가 있고 이를 처리하기 위한 CPU가 있음
• CPU에는 여러 코어가 있고 코어별로 작업 처리 시간이 다름
• 2개 이상의 코어가 남을 경우 앞의 코어부터 작업을 처리한다.
• 처리해야 될 작업의 개수 n과, 각 코어의 처리시간이 담긴 배열 cores가 매개변수로 주어질 때 마지막 작업을 처리하는 코어의 코어 번호를 return 해야 함

DP, 이진 탐색 사용

1. cpu의 core 수를 늘려가며 탐색해 본 결과 time% core == 0 일 때 해당 core가 새로운 일을 처리함
2. time이 m 일 때, m // \( i_{-t} \) + m // \( i_{t} \) + m // \( i_{+t} \)개의 일을 처리할 수 있음

---

이를 토대로 이진 탐색을 이용하여 문제를 해결함

초기에 다음과 같이 left, right를 설정했으나 효율성 문제 때문에 수정함

time을 이진 탐색을 통해 찾고 time에 해당하는 works를 구한다. 이를 n과 비교하여 n이 더 크다면 left = m,  n이 작다면 right = m으로 변경한다.

 

이때 완전히 fit 한 값을 찾는 것이 아니기 때문에 7과 9는 같은 t이 나온다. 여기서 7일 때 t = 2가 나오고 9일 때 t = 3이 나오면서 추가적으로 더해서 계산을 하려고 했기 때문에 w> n일 때 예외 처리를 해준다.

 

end를 10,000으로 주었다가 효율성에서 떨어져서 처리 시간이 오래 걸리는 core * n을 해주어 최대 시간을 넣어줬다.

---

def solution(n, cores):
    start, end = 0, max(cores)*n
    cnt, m = 0, 0
    answer =0

    if n <= len(cores):
        return n
        
    while start+1 < end :
        cnt = 0
        m = (start + end) // 2
        for i in cores:
            cnt += ((m//i) + 1)
        if cnt < n:
            start = m
        else:
            end = m
            
    if n <= cnt:
        cnt = 0
        m = m-1
        for i in cores:
            cnt += ((m//i) + 1)
            
    capacity = n-cnt
    
    for i, c in enumerate(cores,1):
        if (m+1) % c == 0:
            capacity -= 1
            if capacity == 0:
                return i
                
    return answer

---

다른 사람의 풀이

효율성을 고려하지 않았지만 직관적인 풀이가 있었다.

def solution(n, cores):
    remain = [0 for _ in cores]
    print('main',remain)
    while n:
        for i in range(len(cores)):
            if remain[i] == 0:
                n-=1
                if n == 0: return i+1
                remain[i] += cores[i]
        remain = list(map(lambda x: x-1, remain))
        print(remain)

remain에 core 길이만큼의 list를 만들어서 

0이 현재 사용가능한 코어이고 0 이외의 숫자는 코어를 사용하기 위해 남은 시간이다. 이렇게 시간 정보를 넣어서 n이 0이 될 때의 core index를 return 한다.

 

list에 시간 정보를 넣어 제어하는 방식은 다른 문제에서 사용할 수 있을 것 같음