최솟값 찾기 (백준 11003)

문제 링크 : https://www.acmicpc.net/problem/11003

 

문제 분석

1. 정렬을 이용한 문제해결

 일정 범위 안에서 최소값을 구하는 문제이므로 "슬라이딩 윈도우" 방식과 "정렬"을 통해 답을 추리면 결과를 얻을 수 있으나, 정렬 알고리즘의 시간 복잡도는 O(nlogn) 이므로 문제에 효율적이지 못하다.

 

( 문제 상황에서 시간 복잡도는  O(nlogn) 정렬 알고리즘을 포함하면 O((N-L+1) * L log L) 이 되는데 이는 모든 슬라이드에서 정렬을 하여 답을 구하는 경우이다. 따라서, 이 문제를 효율적으로 해결하기 위해서는 정렬을 사용하지 않고, 덱(deque)과 같은 자료구조를 활용하여 O(N)의 시간 복잡도로 해결하는 방법이 좋다.)

정렬 알고리즘 중 비교 기반 정렬 알고리즘은 n 개의 원소를 정렬하는데 O(nlogn)의 시간이 소요된다.

 

2. 덱(deque) 이용한 문제해결

덱(Deque, Double-ended Queue)은 양쪽 끝에서 삽입과 삭제가 가능한 자료구조이다.
큐(Queue)와 비슷하지만,

• 앞에서도(push front) 삽입/삭제 가능
• 뒤에서도(push back) 삽입/삭제 가능

Python에서는 collections.deque 모듈을 사용하면 덱을 쉽게 다룰 수 있다.

 

1. 덱의 맨 앞 요소는 항상 최솟 값.

2. 덱에 값을 추가할 때  덱의 맨 뒤의 요소와 비교, 맨 뒤 요소가 클 경우 맨 뒤 요소를 제거

3. 덱의 윈도우 범위를 벗어나는 맨 앞 원소 제거

 

덱의 맨 앞 요소는 항상 현재 슬라이딩 윈도우 내의 최솟값을 나타내며, O(N) 시간 복잡도로 효율적으로 계산하는 알고리즘이다.

코드

from collections import deque
N, L = map(int, input().split())
arr = list(map(int, input().split()))

dq = deque()
result = []

for i in range(N):
    while dq and dq[-1][0] > arr[i]: #덱의 맨 뒤 요소가 현재 배열의 원소 보다 크다면 제거
            dq.pop()
    
    dq.append((arr[i], i)) #튜플 (인덱스, 값)

    if dq[0][1] <= i - L: #덱의 맨 앞 원소의 인덱스, 윈도우 범위를 벗어난다면 제거
          dq.popleft()

    print(dq[0][0], end=" ")