백준(BOJ) 11003 최솟값 찾기(Python)

문제 내용

 

덱으로 바로 풀 수 있는 문제.

최소 힙으로 최솟값을 뽑아낼 생각이었는데, O(nlogn)이라 그런지 python이랑 pypy 둘 다 시간 초과가 터졌다.

그래서 생각한 게, 덱을 써서 항상 최솟값이 덱 맨 앞에 있도록 하는 것이다.

탐색 범위에 있지 않은 값을 덱에서 빼고, 현재 덱에 삽입될 값보다 큰 값을 가졌으면 덱에서 빼는 식으로 덱을 수정해나갔다.

결국 O(n)으로 해결할 수 있었다.

​

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import copy
#input=sys.stdin.readline
#sys.setrecursionlimit(100000000)

n,l=map(int,input().split())
L=list(map(int,input().split()))
d=deque()
for i in range(n):
    while d and d[0][1]<i-l+1:
        d.popleft()
    while d and L[i]<d[-1][0]:
        d.pop()
    d.append([L[i],i])
    print(d[0][0],end=' ')

 

이렇게 코드를 짜도 python에서는 시간 초과가 터졌다.

pypy로 제출하니 통과했다.

진짜 파이썬 느려가지고 스트레스 받는다.