[백준] 11003번: 최솟값 찾기

백준 11003번: 최솟값 찾기

힙(우선순위 큐) 풀이방법 적어보겠습니다!

1 5 2 3 6 2 3 7 3 5 2 6

위는 예제 입력 1의 수열입니다.

이를 배열 A로 정의하고, 결과를 구하기 위해 for문을 돌면서 힙에 현재위치(i)와 해당 숫자를 넣습니다.

L이 3이기때문에 힙에 3개를 모두 채울때까지(=i가 2일때까지) 넣고, 최소값을 출력합니다.

[(1, 0), (5, 1), (2, 2)]

그러면 힙에 위와 같이 들어갈겁니다.

이제 i가 4인 경우, 힙에 4개가 들어가게됩니다.

[(1, 0), (5, 1), (2, 2), (5, 1)]

i가 4일때 A[1]~A[4]에 있는 값 중 가장 작은 값을 출력해야합니다.

그런데 저희가 처음에 위치를 같이 힙에 넣었었죠?

heap[0]이 (1, 0)이라는 뜻은, 여기서 최소값이 1이지만 이 위치가 0, 즉, 저희가 구하려는 범위(A[1]~A[3])을 벗어난다는 의미입니다. 범위를 벗어났으므로 pop을 해줍니다.

[(2, 2), (3, 3), (5, 1)]

pop을 하면 힙이 이렇게 됩니다. 이제 최소값이 2이고, 해당 최소값의 위치는 2, 구하려고 하는 범위(A[1]~A[3]) 사이에 위치한다는 뜻이죠. 구하려는 값이므로 최소값을 출력해줍니다.

만약 pop을 하고도 구하려는 범위를 벗어난다면 계속 pop을 하면서 위치를 맞춰주시면 됩니다!

*PyPy3로 통과하는 코드입니다.

import heapq
N, L = map(int, input().split())
A = list(map(int, input().split()))

heap = []
for i in range(N):
    heapq.heappush(heap, (A[i], i))
    while heap[0][1] <= i-L:
        heapq.heappop(heap)
    print(heap[0][0], end=' ')