자료구조&알고리즘/프로그래머스
[Python] 디스크 컨트롤러 / 힙
두잇 두두
2024. 2. 10. 23:29
728x90
문제
https://school.programmers.co.kr/learn/courses/30/lessons/42627
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
코드
import heapq
def solution(jobs):
jobs_len = len(jobs)
jobs.sort(key=lambda x:x[0])
heap = []
total_time, current_time = 0, 0
while jobs or heap:
while jobs[0][0] <= current_time:
job = jobs.pop(0)
heapq.heappush(heap, (job[1], job[0]))
print('heap:', heap)
if heap:
processing_time, starttime = heapq.heappop(heap)
current_time += processing_time
total_time += current_time - starttime
else:
current_time = jobs[0][0]
print('totlal_time:', total_time)
answer = total_time // jobs_len
return answer
print(solution(jobs = [[0, 3], [1, 9], [2, 6]]))
다른 사람 코드
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)
접근법
- jobs 리스트를 작업이 요청되는 시점 기준으로 오름차순으로 정렬합니다.
- 현재 시간을 나타내는 변수를 초기화하고, 작업들을 차례로 처리합니다.
- 최소 힙을 사용하여 대기 중인 작업 중 소요시간이 가장 적은 작업을 선택합니다.
- 선택된 작업의 시작 시간이 현재 시간보다 이전이라면, 현재 시간을 시작 시간으로 업데이트합니다.
- 선택된 작업을 수행하고, 걸린 시간을 누적합니다.
- 작업을 처리하는 동안 현재 시간을 업데이트하고, 모든 작업을 처리한 후에는 누적된 시간을 작업의 개수로 나누어 평균을 구합니다.
배운 점
힙을 더 능숙하게 사용 할 수 있게 되었다.