[백준] 11003번 : 최솟값 찾기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

11003번: 최솟값 찾기

 

1. 문제 설명

2. 풀이과정

해당 문제는 일정 범위 안에서 최솟값을 구하는 문제로 슬라이딩 윈도우와 정렬을 사용하면 된다.

윈도우의 크기는 문제에서 최솟값을 구하는 범위가 i - L + 1부터 i까지이므로 L로 생각하면 된다.

최솟값을 찾기 위한 정렬을 O(nlogn)의 시간 복잡도를 가지므로 N과 L의 최대 범위가 5,000,000인 해당 문제에서는 정렬을 사용할 수 없다. O(n)의 시간 복잡도로 해결하기 위해 덱(deque)을 활용해 문제를 해결한다.

 

덱에는 (값, 인덱스) 형태로 저장한다.

덱 안에 원소가 있고, 덱의 제일 뒤에 저장되어 있는 원소의 값이 현재 저장하려는 값보다 크면 최솟값을 구해야 하므로 해당 원소를 제거한다.

큰 값들을 모두 제거하면 현재 범위의 값을 (값, 인덱스) 형태로 덱의 제일 뒤에 추가한다.

만약 제일 앞에 저장되어 있는 원소의 인덱스가 슬라이딩 윈도우의 범위를 벗어났다면 해당 원소를 제거한다.

이런 규칙으로 덱을 채우면 덱의 제일 앞에 저장되어 있는 원소의 값이 해당 범위 안의 최솟값이 된다.

 

슈도코드

1. N(데이터의 개수), L(최솟값을 구하는 범위) 입력받기
2. A(주어진 숫자 데이터를 가지는 리스트)
3. d(데이터를 담을 덱 자료구조)
4. for N만큼 반복
5. 덱의 마지막 위치에서부터 현재 값보다 큰 값은 덱에서 제거
6. 덱의 마지막 위치에 현재 값 저장
7. 덱의 제일 앞 위치에서부터 L의 범위를 벗어난 값을 덱에서 제거
8. 덱의 제일 앞 데이터 출력

반응형

3. 소스코드

import sys
from collections import deque

N, L = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))

d = deque()
for i in range(N):
    while (d and d[-1][0] > A[i]):
        d.pop()

    d.append((A[i], i))
    if (d[0][1] <= i - L):
        d.popleft()

    print(d[0][0], end=' ')