프로그래머스 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'과 같은 구조입니다.
감사합니다.🐇🐇🐇