[python] 프로그래머스 - 디스크 컨트롤러

출처 : 프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/42627

프로그래머스

 

# 작업들이 (요청 시간, 작업 소요 시간) 리스트로 들어온다.
# 디스크는 1개에 1개의 작업만 가능

# 평균 (요청 시간 ~ 작업 종료) 시간이 가장 짧게 프로세싱할 경우 평균 (요청 시간 ~ 작업 종료) 시간을 return

 

 

먼저, 생각해야 할 부분

 

1. jobs가 정렬되어 들어온다는 말이 없다.

    진짜 치사한데, 맞는 말이다. 정렬되어 들어온다는 말이 없으므로 정렬을 해줘야한다.

 

2. 평균 (요청 시간 ~ 작업 종료) 시간이 가장 짧으려면, 대기 중인 작업들 중 소요 시간이 짧은 것부터 하면 된다.

---

 

풀이

 

# 디스크 컨트롤러가 작업을 마치는 시간을 구한다.
    # 종료 시간은 작업 시작 시간 + 작업 진행 시간
# 디스크 컨트롤러가 작업을 마치디 전에 도착한 작업을 jobs에서 빼 heap에 넣는다.
    # heap의 우선 순위는 작업 시간
# 디스크 컨트롤러가 작업을 마치면 heap에서 꺼내 작업을 부여한다.
# 반복

from heapq import heappop, heappush
from collections import deque

def solution(jobs):
    JC = len(jobs)
    time = 0 # 누적 시간
    total_ask_end_time = 0 # 총 요청-처리 시간
    
    jobs = deque(sorted(jobs))
    heap = []

    # 힙 초기화
    ask_time, processing_time = jobs.popleft()
    heappush(heap, (processing_time, ask_time))
    
    # 0초에 시작하지 않을 수도 있으므로
    time += ask_time
    
    while len(heap) > 0:
        cur_processing_time, cur_ask_time = heappop(heap)
        
        # 종료 시간
        time += cur_processing_time
        
        # time보다 전에 들어온 작업을 heap에 넣음.
        while len(jobs) > 0 and jobs[0][0] <= time:
            next_ask_time, next_processing_time = jobs.popleft()
            heappush(heap, (next_processing_time, next_ask_time))
        
        # 요청-처리 시간 누적
        total_ask_end_time += (time - cur_ask_time)

        # 현재 시간까지 도착한 작업이 없다면, 작업이 도착할 때까지 대기 후 새 작업 부여
        if len(jobs) > 0 and len(heap) == 0:
            next_ask_time, next_processing_time = jobs.popleft()
            heappush(heap, (next_processing_time, next_ask_time))
            time = next_ask_time
        
    # 모든 작업이 끝나면, answer를 JC로 // 나눔.
    return total_ask_end_time // JC

---

알게 된 점

 

입력은 마구잡이일 수 있다.

 

순서대로 뽑아야하는 문제라면, 일단 정렬을 꼭 하자.

 

Github

GitHub - bh2980/Algorithm-Problem: 알고리즘 풀이 흔적들