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

문제

문제 링크

대기중인 작업이 하나뿐이면 해당 작업 수행.
현재 시간에 대기중인 작업이 여러개면 종료시간 빠른 작업부터 수행.
jobs 배열은 [시작시간,종료시간] 으로 작업들 저장됨.
작업들의 평균 대기시간 최소값 구하기.

접근방식

1. jobs를 시작시간 빠른놈이 먼저 나오도록 정렬
2. jobs에서 현재 시간에 가능한 작업(시작시간 < 현재시간)을 heapq에 [종료시간, 시작시간] 형태로 삽입. min heap에서 종료시간 빠른놈이 앞에 올 수 있도록 순서를 뒤집어서 삽입한 것.
3. heapq에서 하나씩 빼며 현재시간을 갱신하고. 현재시간-시작시간을 통해 대기시간의 합을 갱신해나간다.

코드

import heapq

def solution(jobs):
    q = [] #q에는 현재 time기준 실행가능한 모든 작업 저장.
    jobs.sort(reverse=True) #시작 시간이 빠른게 뒤로 가도록 정렬. list의 pop 쓰려고.
    length = len(jobs)

    first = jobs.pop() #시작 제일 빠른거.
    q.append((first[1], first[0])) #q에 종료, 시작 넣음. heapq로 종료 빠른거 넣기위해 
    time = q[0][1] #초기 시간: 첫 작업 시작시간

    result = 0 #총 대기시간. 처음엔 0
    while q:
        val = heapq.heappop(q) #종료시간 제일 빠른놈 뺌
        time += val[0] #종료시간만큼 시간 추가
        result += (time - val[1]) #대기시간 결과에 추가
        while jobs: #jobs 순회하면서 현재시간 작업 가능한 놈들 q에 추가
            if jobs[-1][0] > time: 
                if not q: time = jobs[-1][0] 
                #큐가 비었는데 가장빠른 작업 못넣으면. 시간을 바꾸고 가장 빠른 작업 넣는다.
                else: break
            val = jobs.pop()
            heapq.heappush(q, (val[1], val[0]))

    answer = result // length

    return answer

---

분석

• 파이썬의 heapq는 minheap. 리스트나 투플을 원소로하면 앞의 원소 기준으로 minheap이다. maxheap으로 쓸거면 -붙여서 넣고 빼자.

• 문제 조건 중 하드디스크가 작업 수행중이지 않을 때는 가장 먼저 들어온 작업을 처리한다. -> 큐가 비었는데(대기 작업 없을때) jobs의 가장 빠른 작업 못넣는경우, 시간을 해당 작업 시작시간까지 갱신시킨다.