백준 / 최솟값 찾기 / 11003번 / Python(PyPy3 제출)

*문제 출처는 백준에 있습니다.

문제 제목: 최솟값 찾기 / 11003번 (플래티넘 5단계)

문제 사이트: https://www.acmicpc.net/problem/11003

 

문제 설명

---

나의 풀이

import heapq
from collections import deque

def solution(lis, l):
    # 결과
    result = []
    # L를 계산할 deque()
    q = deque()

    for number in lis:
        q.append(number)
        if len(q) == l + 1:
            q.popleft()
            
        # 최소 값을 구할 힙
        heap = list(q)
        heapq.heapify(heap)

        result.append(heapq.heappop(heap))

    return result

N, L = map(int, input().split())
arrangement = list(map(int, input().split()))

D = solution(arrangement, L)

for i in D:
    print(i, end = " ")

이 풀이는 heapify를 반복적을 사용해서 시간 초과가 발생했다.

시간 복잡도는 O(N * L log L) 가 발생한다.

from heapq import heappush, heappop

N, L = map(int, input().split())
arrangement = [0] + list(map(int, input().split()))

# 최소 값을 구할 힙
heap = []

for i in range(1, N + 1):
    heappush(heap, (arrangement[i], i))
    value, index = heap[0]

    while 1 <= index < i - L + 1:
        heappop(heap)
        value, index = heap[0]

    print(value, end = " ")

이 풀이는 배열을 다시 사용하는 작업을 사용하는 코드다.

시간 복잡도는 O(N log N + N * L) 가 나오는 방식을 사용했다.

---

※ 알아야 할 것

https://newkimjiwon.tistory.com/179

[자료구조] 힙(Heap)