[Python] 파이썬 프로그래머스 디스크 컨트롤러

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

프로그래머스

---

나의 풀이

• task를 시작 시간 순으로 정렬함
• 시점이 변화할 때마다 현재 시점 기준으로 가장 길이가 짧은 task를 가져와 처리함
• 이를 반복하여 task를 다 처리할 때까지 반복함
  • 현재 시점에 할 일이 없다면 now를 1씩 더해줘야 함

---

길이가 짧은 task를 가져와 사용해야 했기 때문에 이 부분은 heap을 사용하였다.

filter 쓸 필요 없이 하나씩 비교하면 되는 점과 현재 시점에 할 일이 없다는 경우를 생각하지 못하고 코드를 작성했다가 뒤늦게 추가해서 최적화가 된 코드는 아니다ㅠ

import heapq as hq

def solution(jobs):
    disk_jobs = sorted(jobs, key=lambda x:(x[0],x[1]))
    first = disk_jobs.pop(0)
    end_time, now_time, answer = first[0], first[0]+first[1], first[1]
    disks = []

    while True:
        for j in list(filter(lambda x:x[0] <= now_time , disk_jobs)):
            hq.heappush(disks, [j[1], j[0]])
        disk_jobs = list(filter(lambda x:x[0] > now_time , disk_jobs))

        if disks == []:
            now_time += 1
        else:
            cur = hq.heappop(disks)
            end_time = now_time
            now_time = end_time + cur[0]
            answer += now_time - cur[1]
        if disks == [] and disk_jobs == []:
            break

    return answer//len(jobs)

---

다른 사람의 풀이

• jobs를 정렬하고 시작 시간 순서로 역배치함
• job을 꺼내와서 현재 시각을 구함
• 현재 시각이 job이 없다면 tasks에서 pop()하여 +1 씩 더하지 않고 바로 job을 가져옴

import heapq
from collections import deque

def solution(jobs):
    tasks = deque(sorted([(x[1], x[0]) for x in jobs], key=lambda x: (x[1], x[0])))
    q = []
    heapq.heappush(q, tasks.popleft())
    current_time, total_response_time = 0, 0
    while len(q) > 0:
        dur, arr = heapq.heappop(q)
        current_time = max(current_time + dur, arr + dur)
        total_response_time += current_time - arr
        while len(tasks) > 0 and tasks[0][1] <= current_time:
            heapq.heappush(q, tasks.popleft())
        if len(tasks) > 0 and len(q) == 0:
            heapq.heappush(q, tasks.popleft())
    return total_response_time // len(jobs)