[BOJ] 11003 최소값 찾기

date

Aug 7, 2023

slug

boj-11003

author

status

Public

문제 링크

문제

N개의 수 A1, A2, ..., AN과 L이 주어진다.

Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.

문제풀이

다른 블로그글을 참고해보니 우선순위큐를 사용해서 풀수도있고, 덱을 사용해도 풀수 있다고 하는데,

파이썬 기준으로 덱이 우선순위큐보다 빠르게 풀 수 있다고 한다.

우선 우선순위큐를 사용했을때는

for i~N까지 돌면서 우선순위큐에 {값, 인덱스}를 같이 삽입해주고

매회차마다 최소값의 인덱스가 i-N+1을 넘어간다 즉 작다면 heapq.heappop 연산을 해주어 새로운 최소값을 찾아 출력하면 되는문제

값과 인덱스를 같이넣는 방법은 생각지도 못했다..

pypy3로 하면 통과하는데 python으로하면 무슨짓을 해도 통과가 안된다…

파이썬 문제풀이 코드


import heapq
from collections import deque
import sys
input = sys.stdin.readline

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

li = list(map(int, input().split()))

h = list()
# heapq.push(h, dq.popleft())
for i in range(N):
    # print(h)
    if i-L+1 <= 0:
        heapq.heappush(h, (li[i], i)) # 인덱스랑 같이 묶어줌
        print(h[0][0], end = " ") 
    elif i-L+1 > 0: # 빼줘야함
        heapq.heappush(h, (li[i], i)) #인덱스랑 같이 묶어줌
        while h[0][1] < i-L+1:
            heapq.heappop(h)
            
        print(h[0][0], end= " ")

시간복잡도

O(nlogn)

입력

첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000)

둘째 줄에는 N개의 수 Ai가 주어진다. (-10^9 ≤ Ai ≤ 10^9)

출력

첫째 줄에 Di를 공백으로 구분하여 순서대로 출력한다.

예제 입력


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

예제 출력


1 1 1 2 2 2 2 2 3 3 2 2

알고리즘 분류

자료 구조

우선순위 큐