[Baekjoon Online Judge] 백준 11003번 최솟값 찾기(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 11003번 최솟값 찾기

(Python)

(글쓴날 : 2020.05.15)

 

---

* Baekjoon Online Judge, 백준 11003번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 11003번 최솟값 찾기

---

1) 문제

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

11003번: 최솟값 찾기

---

2) 풀이 과정

* 시간 복잡도 : O(n)

 

N개의 수가 주어지고 특정 범위가 주어질 때, 해당 범위 내에서 최솟값을 구하는 문제입니다.

 

저의 경우, 슬라이딩 윈도우를 적용하였고, Python을 사용했습니다.

먼저, 주어진 N개의 수를 차례대로 탐색해가며 현재 탐색 중인 수와 덱의 저장된 수들을 뒤에서부터 비교하여, 만약, 덱에 저장되어 있는 수가 더 클 경우 해당 값은 최솟값이 될 수 없으므로 덱에서 전부 빼낸 뒤, 현재 탐색 중인 수를 인덱스와 함께 튜플 형태로 덱에 저장하였습니다.

그 후, 이번에는 덱의 앞 부분부터 저장되어 있는 수의 인덱스가 특정 범위에 해당하지 않을 경우를 체크하여, 만약 해당하지 않는다면 앞으로 전부 빼내어 최종적으로 덱의 맨 앞에 있는 수가 특정 범위 내의 최솟값으로 유지되게 하여 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

from collections import deque
import sys
input = sys.stdin.readline
 
N, L = map(int, input().split())
A = list(map(int, input().split()))
dq = deque()
 
for i in range(N):
    while dq and dq[-1][1] > A[i]:
        dq.pop()
    
    dq.append((i, A[i]))
 
    while dq and dq[0][0] < i - L + 1:
        dq.popleft()
        
    print(dq[0][1], end=" ")

---