[Python][프로그래머스] lv3. 디스크 컨트롤러

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

프로그래머스

 

내 코드

import heapq

def solution(jobs):
    answer, now, i, now = 0,0,0,-1
    l = len(jobs)
    pq = []
    jobs.sort(key=lambda x:x[0], reverse=True) 
#도착 시간을 기준으로 내림차순 정렬한다.

    while True:
        while len(jobs) and jobs[-1][0] <= now: 
#마지막에 도착한 작업이 현재 시간보다 적다면
            ms, time = jobs.pop() #pop!
            heapq.heappush(pq, [time, ms]) #heap에 넣기

        if len(jobs) and not len(pq) and now < jobs[-1][0]:
#jobs는 아직 남아있고, pq는 비었을 때 now보다 늦은 작업이 jobs에 있으면
            now = jobs[-1][0]
#가장 늦은 작업의 도착 시간을 now로 설정
        else:
            time, ms = heapq.heappop(pq)
            answer += (now - ms) + time
            now += time #누적하기
            
        if not len(jobs) and not len(pq):
#jobs도 pq도 비어있으면 break
            break

    return answer // l

 

다른 사람의 풀이

import heapq

def solution(jobs):
    answer, now, i, last = 0, 0, 0, -1
    l = len(jobs)
    pq = []

    while i < l:
        # 현재 시간보다 이전에 요청된 작업을 모두 큐에 추가
        for job in jobs:
            if last < job[0] <= now:
                answer += (now - job[0])
                heapq.heappush(pq, job[1])

        if pq:
            answer += (len(pq) * pq[0])
            last = now
            now += heapq.heappop(pq)
            i += 1  
        else:
            now += 1

    return int(answer // l)

 

코드 리뷰

heapq 우선순위 큐

heap이 매우 약하다는 것을 알아버렸다. heap을 언제 사용하는지 어려워하는 내 모습을 보면서 1차 충격을 받았다. heap 좀 열심히 연습해야겠다. 그래서 이번 문제를 풀면서도 주석을 굉장히 열심히 달았다. 이 문제는 뜯어봐야 제맛인 것 같으니 어서 뜯어보자.

 

import heapq

우선 heapq를 import 해주면 heappush, heappop 등의 함수들을 사용할 수 있다. 그리고 만약 PriorityQueue를 사용하고 싶으면, from queue import PriorityQueue를 해주면 된다.

 

def solution(jobs):
    answer, now, i, now = 0,0,0,-1
    l = len(jobs)
    pq = []
    jobs.sort(key=lambda x:x[0], reverse=True)

이건 기본 세팅이다. [[0, 3], [1, 9], [2, 6]] 이런 모습의 jobs라는 list가 기본으로 주어진다. 나는 이 list에서 x[0]값을 기준으로 내림차순 정렬하려고 sort를 했다. 여기서 x[0]은 작업 요청이 들어온 시간인데, 각각의 리스트 중에서 앞에 있는 숫자를 의미한다.

 

while True:
        while len(jobs) and jobs[-1][0] <= now: 
            ms, time = jobs.pop() #pop!
            heapq.heappush(pq, [time, ms]) 

        if len(jobs) and not len(pq) and now < jobs[-1][0]:
            now = jobs[-1][0]

계속 돌리면서, 현재 시간이랑 jobs의 마지막 도착 시간이랑 비교한다. 그리고 마지막에 도착한 작업을 heap에 넣는다. 

 

다음 반복문은 jobs에 한 개 이상의 수가 들어있으면서, pq가 비어있는지를 검사한다. 그리고 현재 시간이 jobs의 마지막 도착 시간보다 작은지를 동시에 검사한다. 현재 시간인 now보다 늦은 작업이 jobs에 있다면 now에 가장 늦은 작업을 지정한다.

여기서 조심할 부분은 만약 not len(pq)를 사용한다면 index error가 발생한다. pq가 비어있을 때 pq를 직접 사용한다면 index error가 발생하기 때문이다. 그러니 반드시 not len(pq) 이렇게 사용하자!

 

        else:
            time, ms = heapq.heappop(pq)
            answer += (now - ms) + time
            now += time

그리고 만약에 pq가 비어있지 않는다면, pop으로 heap에 들어있는 수를 꺼내주고 answer에 걸리는 시간을 계산하여 저장한다. 현재 시간 - 작업 요청 도착 시간 + 소요 시간을 해주면 된다. 누적해서 더해주어야 문제 조건에 일치하니 계속해서 합해주도록 한다. 그리고 현재 시간에는 걸리는 시간을 계속해서 누적해주면 된다. 

 

 if not len(jobs) and not len(pq):
            break

    return answer // l

만약 jobs가 비었고, pq도 텅텅 비었다면 할 연산은 더이상 없는 것이다... 끝내자! 마지막으로 문제 조건에 맞게 누적 소요 시간을 작업의 총 개수로 나누어주면 된다.

 

heapq....공부하자~ heap은 자동으로 정렬을 하기 때문에 가장 큰 수를 빼내거나, 가장 작은 수를 빼낼 때 아주 좋은 도구이다. 잘 이용해보자.

 

Heap에 대한 자세한 설명은 밑에서 볼 수 있다.

[자료구조] 힙(Heap) / 우선순위 큐(PriorityQueue) 파이썬으로 구현하기