[Python]프로그래머스 - 선입선출 프로그래밍 풀이

이희진·2023년 11월 9일
0

Programmers 선입선출 프로그래밍 (12920번)

선입선출 스케줄링 문제, 처리해야 할 작업이 50,000 이하의 n개, 코어의 처리 시간 cores이 주어진다.
CPU에는 여러 개의 코어가 있고, 코어 별로 처리 시간이 다르다. (2 이상 10,000 이하)
작업이 없는 코어 중 앞의 코어부터 작업 처리하며, 마지막 작업을 처리하는 코어의 번호 return 하라는 문제다.

첫번째 풀이

from queue import PriorityQueue

def solution(n, cores):
    que = PriorityQueue()
    running = PriorityQueue()
    time = 0
    dic = {}     
    for idx, c in enumerate(cores):
        que.put(idx)
        dic[idx] = c
    
    for i in range(n):
        while not running.empty():
            t, core = running.get()
            if t <= time:
                que.put(core)
            else:
                running.put((t, core))
                break
              
        if que.empty():
            t, core = running.get()
            time = t
            running.put((time+dic[core], core))  
            
        else:
            core = que.get()
            running.put((time+dic[core], core))
            
        if i == n-1:
            return core+1          

정확성 테스트는 통과, 효율성 테스트는 모두 통과하지 못했다. 시간이 오래 걸리는 반복문 구문을 생각해봤을 때, while문을 없애는 것이 좋겠다는 느낌이 들었다.
굳이 running과 waiting 큐를 쓰지 말고, 종료된 시간(초기는 0)을 잘 기록한다면 하나의 우선순위 큐로 충분히 사용할 수 있을 것이다. 그렇게 수정해보니 코드가 매우 간략해졌다.

두번째 풀이

from queue import PriorityQueue

def solution(n, cores):
    running = PriorityQueue()
    dic = {}     
    for idx, c in enumerate(cores):
        running.put((0, idx))
        dic[idx] = c
    
    for i in range(n):
        time, core = running.get()
        running.put((time+dic[core], core))  
              
        if i == n-1:
            return core+1 

매우 간단해졌음에도 불구하고 시간 초과가 떴다. 작업이 50000개 이하라는 조건에 따라 최대 5만번의 딕셔너리 저장, 5만번의 우선순위큐 get, 5만번의 우선순위큐 put 연산이 일어날 수 있다. 여기서 뭐가 가장 오래 걸릴지 생각해보면, 정렬 연산을 하는 우선순위큐 연산일 것이다. 그렇다면 우선순위큐가 아닌, 힙 자료구조를 사용하면 어떨까? 이진트리 구조를 사용하기 때문에 추가와 삭제가 더 빠를 것이다.

세번째 풀이

import heapq

def solution(n, cores):
    running_list = [(0, n) for n in range(len(cores))]
    
    for i in range(n):
        time, core = heapq.heappop(running_list)
        heapq.heappush(running_list, (time+cores[core], core))  
              
        if i == n-1:
            return core+1  

이번에는 효율성 테스트의 일부 케이스만 시간 초과가 났다. 우선순위 큐를 사용했을 때보다 훨씬 빨라진 것 같지만 결국 여기서 더 시간을 줄이려면 방법을 바꿔야했다. 그래서 구글링을 해보니 이분탐색으로 푸는 방법이 있다는 아이디어를 얻고 코드는 보지 않은 채로 다시 풀어봤다.

네번째 풀이

여러 시도를 하다가 결국 다른 사람의 풀이를 확인했는데, 시간을 이분탐색하는 생각하지 못한 방법이 있었다. 내용은 다음과 같다.

  1. 만약 n값이 cores의 길이보다 작을 경우, n값이 곧 정답이 된다.
  2. 이분탐색을 진행하는데, left는 1로, right은 최대 시간*5, mid 값은 중간의 시간값이 될 것이며, n과 비교할 것은 n-1의 시간동안 처리한 일의 양이다.
  3. 여기서 처리한 일의 양은? 특정 시간(h)에 대해, 새로 수행한 작업 수는 h의 약수인 작업시간을 갖는 cpu들의 sum이다. 그렇다면 각 시간의 처리 작업 수를 알 수 있고, 총 처리 작업 수를 알 수 있으니, n번째를 찾으면 된다.
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

0개의 댓글