[백준/11003] 최솟값 찾기 (Python)

Problem : https://www.acmicpc.net/problem/11003

11003번: 최솟값 찾기

 

Difficulty : Platinum 5

 

Status : Solved

 

Time : 00:18:22

 

---

 

문제 설명

 

 

N개의 수 A1, A2, ..., AN과 L이 주어진다.

Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.

 

 

입력 및 출력

 

입력

 

첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000)
둘째 줄에는 N개의 수 Ai가 주어진다. (-10^9 ≤ Ai ≤ 10^9)

 

출력

 

첫째 줄에 Di를 공백으로 구분하여 순서대로 출력한다.

 

입력 예시

 

12 3
1 5 2 3 6 2 3 7 3 5 2 6

 

출력 예시

 

1 1 1 2 2 2 2 2 3 3 2 2

 

 

---

 

풀이

 

L, N 이 5 * 10^6까지 올 수 있으므로, 대략 D_i의 범위를 산정할때, 그리고 D_i를 계산할 때 모두 O(XlogX)이하의 시간복잡도가 요구된다.

 

D_i의 범위를 산정하는 것은 쉬운 편이다. 선입선출이 가능한 큐 자료구조를 우선 떠올릴 수 있다. 하지만 우리는 이 자료구조 내의(길이가 거의 항상 L인) 최솟값을 항상 알고 있어야 한다. 이 경우는 첫 번째, 우선순위 큐를 사용해 볼 수 있다.

 

우선순위 큐는 항상 최솟값을 O(1) 시간 내에 접근 가능하며, 삽입 및 삭제 한 번에 O(logN)이 소요된다. 즉 최대 O(NlogN)의 시간 내에 해결이 가능하다고 볼 수 있겠다. 유효한 최솟값이 나올 때까지(즉 인덱스 범위가 i-L+1 ~ i내인) 최솟값을 heappop으로 제거하면 된다. 이 점을 고려하여 작성하면 된다.

 

 

풀이 코드(우선순위 큐, pypy3)

from heapq import heappush, heappop

N, L = map(int, input().split())
num_list = list(map(int, input().split()))
dq = list()
D_list = list()

for i in range(N) :
  while dq and dq[0][1] < i - L + 1:
    heappop(dq)
  heappush(dq, (num_list[i], i))
  D_list.append(dq[0][0])
print(*D_list)

 

또한 덱을 떠올려볼 수도 있겠다. 양방향 출입이 가능한 자료구조로, 덱 구조를 이용하여 다음과 같은 알고리즘을 생각해보자.

 

• 우선, 스택을 사용하는 여타 문제들처럼 항상 크기순으로 오름차순이 되는 구조를 유지하도록 하자. 즉 새로운 요소를 넣기 전, 새로운 요소보다 작은 값이 나타날 때까지 덱의 오른쪽 요소들을 pop한다. 즉 이러한 구조 상에서는 가장 왼쪽 요소가 항상 최솟값을 유지하게 된다.
• 또한, 위 구조에서 유효한 최솟값이 나올 때까지(즉 앞서와 같이 인덱스 범위가 유효한 최솟값이 나올 때까지) 덱의 왼쪽 요소를 pop한다. 즉 이 과정을 거치면 최솟값을 유지함과 동시에 이 최솟값의 유효성이 보장된다.

 

덱을 활용하면 삽입, 삭제 모두 선형 시간이 소요되므로 훨씬 빠르게 문제를 해결해 볼 수 있다.

 

풀이 코드(덱, python3, pypy3)

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

풀이 완료!