04/03 코딩테스트 문제풀이 - 디스크 컨트롤러 (프로그래머스) ⭐⭐⭐⭐⭐

문제

• 프로그래머스 알고리즘 문제
• 디스크 컨트롤러
• 문제 내용 : [링크]
  
  
  
  

내가 작성한 코드

from heapq import heappush, heappop
def solution(jobs):
    jobs.sort()
    heap = []
    current_time, completed_jobs, total_response_time = 0, 0, 0
    jobs_idx = 0
    
    while completed_jobs < len(jobs):
        while jobs_idx < len(jobs) and jobs[jobs_idx][0] <= current_time:
            start, duration = jobs[jobs_idx]
            heappush(heap, (duration, start))
            jobs_idx += 1
        
        if heap:
            duration, start = heappop(heap)
            current_time += duration
            total_response_time += current_time - start
            completed_jobs += 1
        else:
            current_time = jobs[jobs_idx][0]
        
    return total_response_time // completed_jobs
          

• 주어진 jobs의 작업을 수행할 때, 작업별 수행까지 걸리는 시간의 평균의 최소값을 구하는 문제이다.

• 작업 수행 시간이 적은 작업 순으로 수행해야 전체 수행시간의 합이 줄어드므로, heap을 활용한다.
  (heap = [])

• 작업요청시작시간 순으로 정렬한다. (jobs.sort())

• current_time, completed_jobs, total_response_time 및 작업 인덱스(jobs_idx) 초기값을 설정한다.

• 아래의 과정을 completed_jobs 가 모든 jobs의 개수와 같아질 때 까지 수행한다.

1. jobs_idx가 jobs 인덱스 범위 안에 있고, 작업 요청시간이 현재시간 이전인 작업들을 heappush하여 우선순위 큐에 추가한다.

2. 이 때, (duration, start) 순서로 heappush 해주어서, duration 기준으로 정렬되도록 한다. (우리는 짧은 작업을 먼저 수행해줘야 한다.)

3. jobs_idx를 1씩 증가시키면서 현재 시간기준 가능한 요청받은 모든 작업들을 우선순위 큐에 heappush 해준다.

4. heap에서 데이터를 하나씩 추출해서, current_time, total_response_time, completed_jobs를 업데이트 해준다.

5. 만약 heap에 데이터가 없는 경우 (초기값 또는 0초에 받은 요청이 없는 경우), current_time을 첫 작업 요청시간으로 업데이트 해준다.

• 이미 각 작업별 요청시간부터 수행완료시간까지 소요된 시간 합의 최소는 우선순위 큐(heap)을 통해 확보했으므로, 모든 소요시간의 합을 copleted_jobs로 나누어 평균을 return 한다.

⭐⭐⭐⭐⭐

1. heap의 활용 (반복마다 최소값의 duration을 가지는 작업을 먼저 수행해야함)