[programmers/py]디스크 컨트롤러

디스크 컨트롤러

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

문제 설명

각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소수점 이하의 수는 버립니다)

풀이

heqp을 이용해서 푸는데 중요한 건 진행 시간이 짧은 순서대로 작업이 실행된다.

# 정답 - 못풀어서 다른 사람 풀이 봄
from heapq import heappush, heappop, heapify

def solution(jobs):
    answer = 0
    hq = []
    l_j = len(jobs)
    heapify(jobs)
    now = 0

    while jobs:
        # 일 추가
        while jobs:
            js, jt = heappop(jobs)
            if now < js: # now < 다음 작업이 시작 시간
                heappush(jobs, [js, jt])
                #now = js # 현재 시간을 다음 작업의 시작 시간 + 진행 시간으로 변경, 진행 시간위 위의 now += t
                break
            else : # 밀린 작업이 있다면
                heappush(hq, [jt, js]) # 그냥 추가      
        
        if len(hq)==0 :
            now += 1
        else:
            t,s = heappop(hq)
            answer += now+t-s
            now += t
    
    while hq:
        t, s = heappop(hq)
        answer += now+t-s
        now += t
    
    return answer // l_j

# 단순한 풀이
def solution(jobs):
    re = 0
    t = 0
    l_j = len(jobs)
    jobs.sort(key = lambda x :x[1])
    
    while len(jobs) > 0:
        for j in jobs:
            if j[0] <= t:
                jobs.remove(j)
                t += j[1] -1
                re += t - j[0] + 1
                break
        t += 1
    return re // l_j
    

# 내 풀이 
from heapq import heappush, heappop, heapify

def solution(jobs):
    answer = 0
    hq = []
    l_j = len(jobs)
    heapify(jobs)

    s,t = jobs.pop(0)
    heappush(hq, [t, s])
    now = s
    # hq를 반복
    while hq:      
        t, s = heappop(hq)
        answer += now + t - s     
        now = now + t
        # 일 추가, 진행 시간이 작은게 먼저 와야해서 a,b -> b,a로 넣어줌
        while jobs:
            js, jt = heappop(jobs)
            
            if now < js: # now < 다음 작업이 시작 시간
                if len(hq) == 0:
                    heappush(hq, [jt, js])
                    now = js # 현재 시간을 다음 작업의 시작 시간 + 진행 시간으로 변경, 진행 시간위 위의 now += t
                    break
                else:
                    heappush(jobs, [js,jt])
                    break
            else : # 밀린 작업이 있다면
                heappush(hq, [jt, js]) # 그냥 추가

    return answer // l_j