프로그래머스 Lv3 힙 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

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

[나의 풀이]

⌛ 시간 초과 (10/100)

import heapq

def solution(jobs):
    answer = 0
    
    length = len(jobs)
    # jobs = sorted(jobs, key=lambda x:x[1])
    jobs = [[x[1],x[0]] for x in jobs]
    heapq.heapify(jobs)
    print(jobs)
    # prior_point = 0
    now = 0
    
    while jobs:
        
        # print("-----------")
        time, point = heapq.heappop(jobs)
        # print(job)
        # print("point : ",point, " time : ",time, "answer : ",answer)
        # now += time
        if now<=point:
            answer += time
            now += time
        else:
        # now += time
            now += time
            answer += now-point
        
        print("point : ",point, " time : ",time, "now :", now, "answer : ",answer)        
        # answer += (now-point)
        
        # prior_point = point
        
    answer /= length
    answer = int(answer)
    return answer

Heap 구조를 활용하여 하드디스크가 처리하는 방식을 구현하는 문제입니다. 한번에 하나의 요청을 처리할 수 있고 [작업이 요청되는 시점, 작업의 소요시간]의 2차원 배열이 입력될 때, 모든 작업의 요청부터 종료까지 걸린 시간의 평균의 최솟값을 구하는 문제입니다.🐪🐪🐪

(1) 최초 구현 시, 시간이 적게 걸리는 작업부터 순차적으로 처리하면 소요 평균 시간이 적어질 것이라는 판단으로 최소 힙 구조에 작업의 소요시간을 기준으로 입력하고 heappop()하는 방식으로 구현하였습니다.

(2) 또 '* 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.' 라는 조건을 만족하기 위해 heappop()된 작업을 모두 수행하고 이후에 요청될 작업을 미리 수행하는 방식으로 구현하였습니다.

하지만 위 (1), (2)을 기반으로 구현할 시, 문제의 의도와 다르게 현재 시간을 기준으로 요청되지 않은 작업도 미리 수행해버리므로 올바른 풀이가 아니였고 이를 해결하는데 오래걸려 다른 풀이를 참고하였습니다.

[다른 사람의 풀이1]

import heapq

def solution(jobs):
    answer, now, i = 0, 0, 0
    start = -1 
    heap = []
    
    while i < len(jobs):
        # 현재 시점에서 처리할 수 있는 작업을 heap에 저장
        for j in jobs:
            if start < j[0] <= now:
                heapq.heappush(heap, [j[1], j[0]])
        
        if len(heap) > 0: # 처리할 작업이 있는 경우
            cur = heapq.heappop(heap)
            start = now
            now += cur[0]
            answer += now - cur[1] # 작업 요청시간부터 종료시간까지의 시간 계산
            i +=1
        else: # 처리할 작업이 없는 경우 다음 시간을 넘어감
            now += 1
                
    return answer // len(jobs)

'나의 풀이'처럼 최소 힙을 활용하여 시간이 적게 걸리는 작업부터 수행하는 방식이였습니다. 하지만 heappush()하는 조건을 이전 작업 수행 시간 ~ 현재시간 내에 둔다는 점이 달랐습니다.🐆🐆🐆

정리하자면 모든 작업을 수행하기 위해 현재 시간까지 요청이 들어온 작업들을 소요 시간순으로 heappush()하고 각 작업별 수행시간을 더하는 방식입니다.

이때, 요청된 작업을 아직 다 수행하지 않은 살태로 시간이 지나 새로 요청될지라도
최소 힙 구조이기 때문에 적은 소요 시간이 걸리는 작업을 먼저 수행한다는 점이 최소 힙 구조를 사용한 포인트였습니다.

[다른 사람의 풀이2]

from heapq import heappush, heappop

def solution(jobs):
    jobs.sort()
    num = len(jobs)
    waiting = [] # (소요시간, 요청시점)
    count = [] # 각 작업이 몇초 걸렸는지
    now = 0 #현재 시각

    while len(count) != num : 
        while jobs and now >= jobs[0][0] : 
            top = jobs.pop(0)
            heappush(waiting, (top[1], top[0]))

        if jobs and waiting == []:
            top = jobs.pop(0)
            now = top[0]
            heappush(waiting, (top[1], top[0]))
  
        x,y = heappop(waiting)
        now += x 
        count.append(now-y)

    return sum(count)//num

입력되는 jobs를 요청된 시간으로 정렬하여 현재 시간이하인 작업들을 최소 힙에 heappush()하는 방식입니다.

또

if jobs and waiting == []:
	top = jobs.pop(0)
    now = top[0]
    heappush(waiting, (top[1], top[0]))

와 같은 표현방식으로

현재 시간까지 요청된 작업을 모두 수행한 뒤 다음작업까지의 텀이 있는 경우에는, 인위적으로 현재시간을 이후에 시작해야할 작업 요청 시간으로 초기화하고 수행하는 풀이였습니다.

결과적으로 '다른 사람의 풀이1'과 같은 구조입니다.

감사합니다.🐇🐇🐇