1. 문제 설명

디스크 컨트롤러

2. 문제 분석

job을 처리할 때까지 걸린 time 안에 다른 job 요청이 들어온다면, 이 job을 처리하는 평균 처리 시간을 최소로 만들기 위해서는 요청 시간 순서대로가 아니라 소요 시간 순서대로 정렬해야 한다. 즉 정해진 조건으로 리스트(또는 힙) 안의 값들을 재정렬한 채로 다시 넣어야 한다.

1. jobs을 요청 시간 순서대로 정렬한다. 선택 기준은 FIFO
2. 현재 처리 중인 job을 통해 time을 나타내는 커서를 정할 수 있다.
3. 커서가 가리키는 시간 내에 다른 요청이 들어온지 확인한다.
4. 여러 개라면 요청 시간이 아니라 소요 시간이 짧은 순서대로 정렬한다.

• job 목록을 정렬하고 그 안의 값들을 다시 기준에 맞춰 정렬한 채 넣으면 처리하기 편한 문제이다. 이때 리스트로 한 번, 힙으로 한 번 문제를 풀어 봤는데, 코딩하기 편한 건 역시 리스트가 가장 편했다. 힙은 자동으로 min으로 재배열이 되기 때문에 위처럼 정렬 순서를 유지한 채로 넣으려면 다른 자료구조를 택해야 했기 때문이다.

3. 나의 풀이

1. 리스트로 풀기

def solution(jobs):
    jobs.sort()
    # 요청 시간 기준 정렬
    total = 0
    jobs_num = len(jobs)
    cur_time = jobs[0][0]
    tmp = []
    while jobs:
        req, taken = jobs.pop(0)
        cur_time += taken
        total += cur_time - req
        # 요청된 job은 곧바로 처리 가능
        # 현재 시간: += 소요 시간, 전체 처리 시간: += (현재 시간 - 요청 시간)

        while jobs and jobs[0][0] < cur_time:
            tmp.append(jobs.pop(0))

        tmp.sort(key=lambda x:x[1])
        jobs = tmp + jobs
        tmp = []
            # 현재 작업 중인 job 이외에 cur_time까지 요청 들어온 job을 소요 시간에 따라 정렬

    return total // jobs_num

2. 힙으로 풀기

import heapq
def solution(jobs):
    jobs.sort()
    # 요청 시간 기준 정렬
    total = 0
    jobs_num = len(jobs)
    cur_time = jobs[0][0]
    heap = []

    while jobs:
        req, taken = jobs.pop(0)
        cur_time += taken
        total += cur_time - req
        # 요청된 job은 곧바로 처리 가능
        # 현재 시간: += 소요 시간, 전체 처리 시간: += (현재 시간 - 요청 시간)

        while jobs and jobs[0][0] < cur_time:
            req, taken = jobs.pop(0)
            heapq.heappush(heap, [-taken, req])
        while heap:
            taken, req = heapq.heappop(heap)
            jobs.insert(0, [req, -taken])
            # 현재 작업 중인 job 이외에 cur_time까지 요청 들어온 job을 소요 시간에 따라 정렬

    return total // jobs_num