[Programmers] 디스크 컨트롤러 (Python)

문제

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

프로그래머스

 

풀이과정

처음에는 작업 요청이 들어온 시점과 현재 작업을 처리해야 하는 시점을 고려하지 않고 job으로 들어온 전체 작업에 대해 한번에 정렬을 수행해서 실패함. 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.라는 제한사항이 있었는데 문제에 대한 이해도가 낮았음. 

본 문제의 유형이 Heap으로 분류되어 있어 힙정렬을 사용하기는 했지만, 문제 핵심이 그때그때 최소 또는 최댓값을 찾아야 한다면 바로 힙정렬을 적용하면 될 것 같다.

1. 현재 시점을 기준으로 처리 가능한 작업을 힙에 넣는다.
- 현재 시점에 처리 가능한 기준 : 이전 작업의 작업 완료 시간 < 작업 요청시간 <= 현재 시점
- heappush 기준 : 입력받는 값이 [작업 요청 시점, 작업 소요 시간]이므로 해당 순서를 바꿔 정렬이 '작업 소요 시간'을 기준으로 수행될 수 있도록 한다.

2-1. 힙에 처리할 작업이 있다면 index 0 인 값을 빼서 현재 시점, 총 소요시간 등을 구해주는 모든 작업을 수행한다.

2-2. 힙에 처리할 작업이 없다면 현재 시점에서 1을 증가시킨다. (1ms 경과)

 

Script

import heapq

def solution(jobs):
    
    job_list = []
    start = -1
    now = 0 # 현재시점
    answer = 0
    i = 0

    while (i < len(jobs)):
        for job in jobs:
            if start < job[0] <= now:
                heapq.heappush(job_list, (job[1], job[0]))  #작업 대기 시간순 정렬

        if job_list: # 현재 처리하는 작업
            cur_work = heapq.heappop(job_list) # heap min값 꺼냄
            start = now
            now += cur_work[0] # 현재 시점 + 현재 처리 할 작업의 소요 시간 -> 작업이 종료될 절대시간
            answer += (now - cur_work[1]) # 작업 종료 시간 - 작업 요청 시간 = 해당 작업의 요청~종료시간 => 누적
            i += 1
        else: # 현재 처리할 수 있는 작업이 없다면
            now += 1 # 시간 1ms 추가
    
    return answer//i