[BOJ] Q11003 최솟값 찾기

[BOJ] Q11003 최솟값 찾기

Question

Language: Python

Difficulty: Platinum 5

해당 문제는 Deque의 성질을 활용하여 풀이하는 유형의 문제이다. Deque는 양쪽에서 삽입/삭제를 처리할 수 있는 자료구조인데, Python의 경우 내부 구현이 linked list 형태로 되어 있어 삽입/삭제 연산 과정이 O(1)의 시간복잡도를 가지므로 매우 빠르다.

문제의 핵심 연산은 아래의 그림을 보면 알 수 있다.

새로운 숫자 삽입

새로운 숫자를 추가할 때는 덱의 뒷부분에 삽입을 하게 되는데, 이때 삽입하고자 하는 숫자보다 앞에 큰 숫자가 있는 경우, 해당 숫자들을 제거한다. 가장 마지막에 들어가는 숫자는 가장 오랫동안 덱에 남아있게 되고, L 구간에서 최솟값을 유지하는 것이 관건이므로 앞의 큰 숫자들은 의미가 없게된다.

while queue and queue[-1][0] >= numbers[i]:
    queue.pop()

숫자 제거

맨 마지막 인덱스 - 맨 첫번째 인덱스를 통해 덱이 참조하고 있는 범위를 구해서 L보다 크게 되면 그 만큼 앞에서 숫자들을 제거한다.

while queue and i-queue[0][1] >= l:
    queue.popleft()

Solution

from collections import deque

def solution():
    queue=deque()

    for i in range(n):
        while queue and queue[-1][0] >= numbers[i]:
            queue.pop()
        while queue and i-queue[0][1] >= l:
            queue.popleft()
        queue.append((numbers[i],i))
        print(queue[0][0])

if __name__ == "__main__":
    n,l=map(int,input().split())
    numbers=list(map(int,input().split()))

    solution()