[프로그래머스] [Python] Level3_디스크 컨트롤러

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

코딩테스트 연습 - 디스크 컨트롤러

1차 시도

import heapq

def solution(jobs):
    jobR = []
    jobs.sort()
    sum = jobs[0][1] #총 수행시간
    
    for i in range(1, len(jobs)):
        jobR.append(list([jobs[i][1], jobs[i][0]]))
    # print(jobR) #[소요시간,요청시점]
    
    while(jobR):
        heapq.heapify(jobR)
        min = heapq.heappop(jobR)
        sum += (sum-min[1])+min[0]

    sum += (-1)*(len(jobs)-2)
    
  	return sum/len(jobs)

 

완료시점-요청시점으로 하면 수행시간이 바로 나오는 것을

시작시점을 구하고 거기서 요청시점을 빼서 대기시간을 더하고 다시 소요시간을 더하는 복잡한 계산식을 머리만 아팠다

 

그래서 아이디어는 그냥 두고 시점 point를 구하는 방식으로 다른 사람의 코드 참고

2차 시도

import heapq

def solution(jobs):
    heap = []
    start = -1 #이전작업 시작시점
    now = 0 #현재시점
    i, ans = 0, 0
    
    while i < len(jobs):
        for j in jobs:
            if start < j[0] <= now: #현시점에 들어와있는지 확인
                heapq.heappush(heap, [j[1], j[0]]) #[소요시간, 요청시점]
        if len(heap) > 0: #지금 작업할 수 있는게 있으면
            min = heapq.heappop(heap)
            start = now
            now += min[0]
            ans += (now-min[1]) #작업완료시점-요청시점=수행시간
            i += 1
        else:
            now += 1
    return int(ans / len(jobs))

 

minHeap을 만들 때, 소요시간이 짧은 것 기준으로 만들어야해서 앞뒤 바꿔서 저장하는 것까진 좋았는데

💡최종로직

0. 현재시점, 이전작업시점 = 0으로 초기화

1. jobs를 한 번씩 돌면서

  1-1 jobs안 요소들 중 이전작업시점 이후, 현 작업시점 이전에 요청시점이 있는 것들은

    1-1-1. jobs안에 주어진 [요청시점, 소요시간]을 [소요시간, 요청시점]으로 heappush한다. 

    (minHeap에 소요시간 기준으로 활용하기 위함)

  1-2. 지금 작업할 수 있는게 heap에 있으면 min pop

    1-2-1. 이전작업시점을 now로 update

    1-2-2. now에 min의 소요시간을 더해서 update

    1-2-3. ans에 (작업완료시점-요청시점), 즉 수행시간을 더해서 update

    1-2-4. i += 1

  1-3. 지금 작업할 수 있는게 없으면, now += 1

2. ans를 len(jobs)로 나눠서 평균값 return

 

시간으로 계산해서 모르겠으면 시점만 구해서 마지막에 계산하자

계산식을 가장 간단히 나타내는 방식을 찾을 것