❓프로그래머스 : 디스크 컨트롤러
📈 문제 설명
각 작업에 대해 [작업 요청 시점, 작업 소요 시간]을 담은 2차원 배열이 주어질 때, 작업의 요청으로부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 구하면 되는 문제
🤨 접근법
대표적인 그리디 문제 유형중 하나인 회의실 배정 문제와 비슷한 유형의 문제이다. 어떤 작업이나 스케줄의 시작시간, 종료시간(혹은 소요시간)이 주어질 때 모든 job을 효율적으로 배치하는 방법은 종료시간(소요시간)을 빠른 순으로 그리디하게 배치하는 것이다.
이를 위해서 힙을 활용했고, 파이썬의 heapq 모듈을 사용했다.
heapify(jobs)
can_do = []
time, answer = 0, 0
while jobs and jobs[0][0] <= time:
request, process = heappop(jobs)
heappush(can_do, (process, request))매개변수로 주어진 작업들(jobs)에 대해 heapify해주어 힙으로 만든 후 현재 시간에서 수행할 수 있는 작업들을 별도의 힙(can_do)로 관리한다. 이때 소요 시간이 가장 적은 작업부터 수행할 수 있어야 하므로 (시작시간, 소요시간)으로 주어진 작업을 (소요시간, 시작시간)으로 바꾸어 힙에 넣는다. 이때 중요한 점은 현재 시점에서 수행할 수 있는 작업만을 넣는 것이다. 위 패턴은 힙을 활용하는 문제에서 자주 나오는 패턴이다.
if can_do:
process, request = heappop(can_do)
done = time + process
answer += (done - request)
time = done
else:
break이제 현재 시점에서 수행할 수 있는 작업 힙(can_do)에서 작업들을 하나씩 heappop하여 작업을 수행한다. 이때 힙은 최소힙이므로 수행 시간이 가장 적은 시간부터 수행된다. 작업을 꺼내어 현재시간에 소요시간을 더해 종료 시간을 구하고, 종료시간 - 작업 요청 시간을 결과 변수에 합산한다. 그리고, 현재 시간을 작업 종료 시간으로 업데이트 해준다.
만약 이때 수행할 수 있는 작업이 없다면 모든 작업을 수행한 것이 되므로 break로 반복문을 탈출한다.
if not can_do and jobs:
time = jobs[0][0]
continue이때 문제가 있다. 만약 작업이 [[0, 3], [5, 7]]같이 주어지면 첫번째 작업이 끝나서 현재 시간이 3이 되면 다음 작업 [5, 7]을 현재 시점에서 수행할 수 있는 작업 힙(can_do)로 넣지 못하게 되어 그냥 종료해버린다. 따라서 작업이 남아있는데 현재 시점에서 수행할 수 있는 작업이 없다면, 현재 시간을 다음 작업의 시작시간으로 바꿔주고 다시 반복한다.
🔡 코드
from heapq import heappush, heappop, heapify
def solution(jobs):
n = len(jobs)
heapify(jobs)
can_do = []
time, answer = 0, 0
while True:
while jobs and jobs[0][0] <= time:
request, process = heappop(jobs)
heappush(can_do, (process, request))
if not can_do and jobs:
time = jobs[0][0]
continue
if can_do:
process, request = heappop(can_do)
done = time + process
answer += (done - request)
time = done
else:
break
return answer//n