📋 문제 정보

문제 요약

응답시간의 평균이 가장 작을 때 평균을 소수점을 버려서 반환

🤔 아이디어

핵심 알고리즘

현재 시간에 들어온 요청이 있다면 모두 최소힙에 저장한다. 이때, 최소힙의 기준은 소요시간이다. 소요 시간이 가장 짧은 요청부터 처리해야 후보의 수를 최대한 줄일 수 있기 때문이다.

현재 힙에 후보가 5개 있을 경우 단순히 계산하면 1초당 응답 시간이 5초씩 늘어난다. 따라서 후보의 수를 빠르게 줄일 수 있도록 소요시간이 짧은 요청부터 처리한다.

의사 코드

# jobs를 시작 시간 순으로 정렬

# jobs 혹은 heap을 모두 소모할 때까지
    # 현재 처리할 수 있는 요청 모두 힙에 넣기
    # 힙이 비어있다면 1초 째깍
    # 힙 소모
        # 현재 시간 갱신
        # 응답 시간 갱신

시간 복잡도

단계별 시간 복잡도는 다음과 같다.

  • jobs 정렬: $O(nlogn)$
  • 전부 소모: $O(n)$

    • 현재 처리할 수 있는 요청 모두 힙에 넣기: $O(k)$

      $k$: jobs에 남아있는 $n$의 수

    • 1초 째깍: $O(1)$
    • 힙 소모: $O(log(n-k))$

따라서 전체 시간 복잡도는 $O(nlogn)$이다.

🖨️ 입출력 분석

시간 복잡도 분석

  • 사실 $n$이 500이하이므로 힙을 사용하지 않고 시간 복잡도가 더 큰 풀이도 가능하다.

추가 테스트 케이스

[[2, 7]]
-> 7

[[0, 1], [0, 3], [0, 5]]
-> (1 + 4 + 9 = 14) / 3 = 4

[[1, 3], [11, 33], [50, 5]]
-> (3 + 33 + 5 = 41) / 3 = 13

[[1, 9], [2, 5], [3, 4]]
-> (9 + 17 + 11 = 37) / 3 = 12

💭 생각 정리

힙을 하나만 소모해야한다

처음에 짠 코드는 한 번의 while문에서 모든 힙을 소모했다. 그러나, 한 번에 하나만 소모해야한다. 예를 들어 7초에 다음과 같은 요청이 힙에 있다고 가정하자.

[[7, 10], [7, 20]]

이때 [8, 1]이라는 요청이 있다면 어떨까? 한 번에 모두 소모한 경우 다음과 같이 동작한다.

[7, 10] -> [7, 20] -> [8, 1]

의사 코드에서 의도한 대로라면 가장 짧은 요청부터 처리해야하는데 그렇지 못하다. 따라서, 한 번에 하나씩 소모한 후 힙을 업데이트해야한다.

📄 소스 코드

from heapq import *

def solution(jobs):
    n = len(jobs)
    
    # jobs를 시작 시간 순으로 정렬
    heapify(jobs)    
    
    heap = []
    now, res = 0, 0
    # jobs 혹은 heap을 모두 소모할 때까지
    while jobs or heap:
        # 현재 처리할 수 있는 요청 모두 힙에 넣기
        for req, time in find_targets(jobs, now):
            heappush(heap, (time ,req))
            
        # 힙이 비어있다면 1초 째깍
        if not heap:
            now += 1
            
        # 힙 소모
        if heap:
            time, req = heappop(heap)
            
            # 현재 시간 갱신
            now += time
            
            # 응답 시간 갱신
            res += now - req
    
    return res // n

def find_targets(jobs, time):
    if not jobs:
        return []
    
    targets = []
    while jobs:
        if jobs[0][0] > time:
            break
        targets.append(heappop(jobs))
        
    return targets