자료구조&알고리즘/프로그래머스

[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)

 

 

 

접근법

 

  1. jobs 리스트를 작업이 요청되는 시점 기준으로 오름차순으로 정렬합니다.
  2. 현재 시간을 나타내는 변수를 초기화하고, 작업들을 차례로 처리합니다.
    1. 최소 힙을 사용하여 대기 중인 작업 중 소요시간이 가장 적은 작업을 선택합니다.
    2. 선택된 작업의 시작 시간이 현재 시간보다 이전이라면, 현재 시간을 시작 시간으로 업데이트합니다.
    3. 선택된 작업을 수행하고, 걸린 시간을 누적합니다.
  3. 작업을 처리하는 동안 현재 시간을 업데이트하고, 모든 작업을 처리한 후에는 누적된 시간을 작업의 개수로 나누어 평균을 구합니다.

 

 

 

배운 점

힙을 더 능숙하게 사용 할 수 있게 되었다.