BOJ 11003 최솟값 찾기

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

11003번: 최솟값 찾기

문제

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)

 

풀이

크기 L인 부분구간의 최솟값을 모두 찾는 문제이다. 처음 봤을때는 슬라이딩 윈도우로 풀어야 할 것 처럼 생겼다. 

"최솟값을 아주 빠르게 찾을 수 있고, 원하는 값을 아주 빠르게 제거할 수 있는" 자료구조가 있으면 된다. 일단 슬라이딩 윈도우로 작은 크기의 문제를 풀어보자. 시간복잡도는 O(N*L)이다.

 

1

5

2

3

6

2

3

7

3

5

예제의 앞 10개항이다.

D1은 [1]의 최솟값 1이다. D2는 [1,5]의 최솟값 1이다. D3은 [1,5,2]의 최솟값 1이다. D4는 D3을 구할 때 썼던 [1,5,2]에서 맨 앞의 1을 제거하고 뒤에 3을 붙인 [5,2,3]의 최솟값 2이다.  D5는 D4를 구할 때 썼던 [5,2,3]에서 맨 앞의 5를 제거하고 뒤에 6을 붙인 [2,3,6]의 최솟값 2이다. ...

이제 관찰을 해보자. 슬라이딩 윈도우 안에 삽입된 수열의 항은 L번의 최솟값 산출 후 제거된다. 이 슬라이딩 윈도우에 삽입된 수는 삽입된 순서대로 제거된다. 즉, 큐를 이용해 해결할 수 있을 것으로 보인다. 

D3을 구할 때 5 뒤에 2가 삽입되었다. 5는 2보다 먼저 제거되는데, 제거되기까지 슬라이딩 윈도우에는 5보다 작은 2가 항상 존재하므로 5는 답이 될 수 없다. 따라서, D3을 구할 때 굳이 5가 슬라이딩 윈도우 안에 있을 필요가 없다. 따라서 위의 해결과정을 살짝 수정하자. 

D1은 [1]의 최솟값 1이다. D2는 [1,5]의 최솟값 1이다. D3은 [1,2]의 최솟값 1이다. D4는 D3을 구할 때 썼던 [1,2]에서 맨 앞의 1을 제거하고 뒤에 3을 붙인 [2,3]의 최솟값 2이다.  D5는 D4를 구할 때 썼던 [2,3]에서 맨 앞의 5를 제거하고 뒤에 6을 붙인 [2,3,6]의 최솟값 2이다.

이 과정을 보편적으로 설명하면, 슬라이딩 윈도우 중 현재 단계에서 새로 삽입될 수 보다 작은 값을 미리 제거할 수 있다는 것이다. 즉, 슬라이딩 윈도우의 가장 마지막 항 보다 큰 수는 슬라이딩 윈도우에서 미리 제거할 수 있다. 하지만, 이 과정을 전 과정에 동일하게 적용한다면, 가장 뒤의 원소를 삽입하기 이전에도 이전의 가장 마지막 항보다 큰 수는 슬라이딩 윈도우 안에 없고, 귀납적으로 슬라이딩 윈도우는 정렬되어있다.

 

정렬되어있는 슬라이딩 윈도우는 큰 값이 뒤에 위치한다. 이때 이 슬라이딩 윈도우의 제일 뒤에 값을 삽입하려한다. 이때 새로 삽입되는 숫자보다 큰 숫자가 존재한다면, 슬라이딩 윈도우의 제일 끝의 원소는 새로 삽입될 숫자보다 자명하게 크다. 따라서 가장 마지막 원소를 제거하고 다시 판단하면 된다. 즉, 슬라이딩 윈도우의 가장 나중에 삽입된 원소를 제거하는, 스택의 쿼리도 지원해야 한다.

 

이 슬라이딩 윈도우가 제공해야 할 쿼리는 제일 앞의 원소를 제거하고, 제일 위의 원소를 추가하거나 제거하는 쿼리이고, 덱으로 쉽게 구현할 수 있다.

 

정리하면, i번째 항 Ai를 슬라이딩 윈도우에 추가하기 위해서, Ai-L을 슬라이딩 윈도우에서 제거한다. 이 제거과정은 삽입되는 순서대로 원소를 제거하는 과정이므로 덱의 제일 앞에 있거나 그 전에 이미 제거되었을 것이다. 따라서 덱의 제일 앞에 있는 경우에는 제거하고, 아니면 그냥 넘어간다. Ai를 추가하기 전, 덱의 제일 뒤에서 Ai보다 큰 값들을 모두 제거한다. 그리고 Ai를 덱에 넣고, 제일 앞의 값이 Di가 된다.