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

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/42627

코딩테스트 연습 - 디스크 컨트롤러

문제 설명

- 각 작업의 시작 시점, 걸리는 시간이 주어짐

- 이들을 "특정 순서"로 진행하면 평균적인 대기 시간(=전체 대기 시간) 을 최소화할 수 있다.

- 이때 대기 시간은 시작 시점~종료된 시점 으로 계산

- 대기 시간을 최소화해봤을 때 평균 값을 구해봐라

 

문제 풀이

• 풀이는 참 간단한데 구현에서 좀 까다롭다
• 우선, 풀이에서 사용할 자료구조는 2개이다. deque(사실 queue 도 상관없음), heap
• deque는 "시작 시점" 기준으로 전체 데이터를 정렬한다
  • 대기열에 들어오는 순이기 때문이다
• heap에서는 "작업 시간" 이 짧게 걸리는 순으로 우선순위 큐를 구성한다
• 기본적인 알고리즘은 "현재 시점에서 가능한 작업들 중 가장 짧게 걸리는 작업을 선택" 하는 것이다
• 왜 가장 짧은 것을 선택해야하는지는 명확하다
  • 이미 대기열에 여러 작업들이 존재할 때, 시간이 오래 걸리는 작업을 선택한다고 가정,
  • 뒤의 작업들은 무조건 해당 오래 걸린 작업 시간만큼 피해를 보기 때문에 광역딜 처럼 적용됨
  • 즉, 먼저 고르는 작업의 시간이 광역으로 넓게 적용되므로, 최대한 짧은 것부터 선택해야 함
• 이와 관련해서 간단한 예외처리, 전처리가 필요하다
  • 시작 시점이 안맞는 경우: 현재 시간에 해당 작업은 대기열에 없다, 따라서 힙에 추가하지 않아야함
  • 힙이 비어 있는 경우: 모든 작업들이 대기열에 없다. -> 쓱 뛰어넘겨도 무방
• 시간의 계산은 다음과 같이 처리하면 됨
  • 현재 시간 += 작업 시간
  • 전체 대기 시간 += 현재 시간 - 작업 대기 시작 시간

 

코드

import heapq
from collections import deque

def solution(jobs):
    answer = 0
    jobs = deque(sorted(jobs))

    current_time = 0
    total_time = 0

    cnt = len(jobs)

    temp_cnt = 0
    temp_index = 0
    temp_pq = []
    
    while temp_cnt < cnt:
        
        # 예쁜 반복문 때려치고 인덱스로 접근하자
        # 인덱스 문제 없고, 시작 시간에 문제 없을 때
        while(temp_index < cnt and jobs[temp_index][0] <= current_time):
            heapq.heappush(temp_pq, (jobs[temp_index][1], jobs[temp_index][0]))
            temp_index +=1
        
        # 작업 다 끝났는데(혹은 앞에서 찾아봤는데) pending 된게 없다 -> 이동
        if(len(temp_pq)==0):
            current_time = jobs[temp_index][0]
        else:
            work_time, start_time = heapq.heappop(temp_pq)
            current_time += work_time
            answer += current_time - start_time
            temp_cnt+=1

    return int(answer/cnt)

 

기타

• Pythonic 하게 반복문 로직을 짜보려고 했는데, 좀 많이 꼬여서 인덱스로 접근했다
• 우선순위 큐에 넣은다음에는 원래 배열에서 제거해주려고 했는데(=작업 완료니깐) 그 부분을 못 구현했다.
• 그래서 선형으로 인덱스를 추가하면서 순회하는 식으로 변경
• 좀 더 깔끔하게 짠 분이 있으면 알려주면 좋겠다. 너무 이상하게 짜버림