[프로그래머스] [힙(Heap)] Lv.3 /디스크 컨트롤러 (파이썬/Python)

1. 문제 설명

2. 코드 

import heapq

def solution(jobs):
    jobs = sorted([[s,l,i] for i, (s,l) in enumerate(jobs)],key=lambda x: x[0])
    heap = []
    time, total_time, idx, done = 0,0,0,0
    n = len(jobs)
    
    while done < n:
        while idx < n and jobs[idx][0] <= time:
            start, length, job_id = jobs[idx]
            heapq.heappush(heap, (length,start,job_id))
            idx += 1
        if heap:
            length, start, job_id = heapq.heappop(heap)
            time += length
            total_time += (time - start)
            done += 1
        else:
            time = jobs[idx][0]
    return total_time//n

3. 풀이 과정

• 자투리 상식 : 힙(Heap)과 heapq 모듈
  - heapq는 리스트를 최소 힙으로 다룰 수 있게 해주는 파이썬 표준 라이브러리
  - 최소 힙(Min-Heap) 구조에서는 항상 가장 작은 값이 루트(맨 앞)에 위치한다.
  - heapq는 다음과 같은 연산을 제공한다.
  heapify() : 리스트를 힙 구조로 바꿈
  heappop() : 가장 작은 값을 꺼냄
  heappush() : 새 값을 넣고 힙 구조 유지

주어진 jobs=[[요청시각,작업시간],...]에서 각 작업의 평균 반환 시간의 정수 부분을 구해야 한다.

jobs 리스트를 요청 시각 순으로 정렬한다.

먼저 들어온 작업부터 확인하기 위해 sorted(jobs,key=lambda x: x[0])를 진행한다.

작업 번호를 붙여 [요청시각,작업시간,작업번호] 형태로 변환하기 위해 enumerate(jobs)를 진행한다.

time, total_time,idx,done 카운터를 초기화한다.

time은 현재 시간, total_time은 총 반환 시간 누적값, idx은 아직 대기큐에 넣지 않은 작업의 인덱스, done은 완료한 작업 수를 의미한다.

while문 시작은 모든 작업이 처리될 때까지 반복한다.

현재 시간 이하로 요청된 작업들을 모두 힙에 추가한다.

힙에는 (작업시간, 요청시각, 작업번호) 형태로 저장하여 작업시간 기준으로 우선순위 적용한다.

이후 힙에서 작업을 꺼내 처리한다.

heappop()으로 가장 짧은 작업을 꺼내 처리한다.

현재 시각을 소요 시간만큼 더하고, 반환 시간을 누적으로 계산한다.

대기큐가 비어 있고, 다음 작업이 아직 오지 않았다면 시간을 다음 작업의 요청 시각으로 건너뛴다.

모든 작업이 끝나면 평균 반환 시간으로 반환한다.

4. 추천 코드

import heapq
from collections import deque

def solution(jobs):
    tasks = deque(sorted([(x[1], x[0]) for x in jobs], key=lambda x: (x[1], x[0])))
    q = []
    heapq.heappush(q, tasks.popleft())
    current_time, total_response_time = 0, 0
    while len(q) > 0:
        dur, arr = heapq.heappop(q)
        current_time = max(current_time + dur, arr + dur)
        total_response_time += current_time - arr
        while len(tasks) > 0 and tasks[0][1] <= current_time:
            heapq.heappush(q, tasks.popleft())
        if len(tasks) > 0 and len(q) == 0:
            heapq.heappush(q, tasks.popleft())
    return total_response_time // len(jobs)

 

5. 추천 코드의 풀이 과정

deque를 사용하는 방법