BOJ : 11003 최솟값 찾기

---

[BOJ 11003(P5)리뷰]

문제는 매우 간단하다. (하지만 푸는건 간단하지 않음 ..)

N개의 수와 정수 L이 주어진다.

각각의 원소마다 자신의 앞과 자신의 앞을 포함하여 L개의 원소 중 최솟값을 출력하면 된다.

예를들어 N=8이고 [1,5,2,3,6,2,3,7] L이 3이라면 

1 -> 최솟값 : 1
1,5 -> 최솟값 : 1
1,5,2 -> 최솟값 : 1
5,2,3 -> 최솟값 : 2
2,3,6 -> 최솟값 : 2
3,6,2 -> 최솟값 : 2

이런식으로 최솟값을 출력하면된다.
창틀을 정해놓고 그 창틀을 조금씩 이동하는것처럼 보이기도 하여 슬라이딩 윈도우라고도 한다.

일단 각각의 원소마다 자신의 앞에 있는 수를 탐색하는 O(N^2)으로는 절대 안풀리고 힙이나 BST를 이용한 O(NlogN)으로도 풀리지 않는다..

즉 이 문제는 O(N)에 해결해야 하는 문제이다. 원소를 한번씩 훑는것만해도 N번이 필요한데 이걸 어떻게 O(N)에 푼단말인가 ..?

답은 "덱"에 있었다.
문제에서 요구하는 "범위 중 최솟값"을 구하는 특성과, front와 back의 삽입/삭제 연산을 O(1)에 할 수 있는 "덱"을 이용하여 이 문제를 해결할 수 있다.

우리는 각각의 범위에서 가장 작은 값만 출력하면 된다. 그렇다면 절대로 출력될 가능성이 없는 값들을 기억해야할 필요가 있을까??자신이 속한 범위에서 자신의 값이 절대로 출력되지 않을것이라면 굳이 그걸 기억해야할 필요가 없다.

이 점을 잘 기억하면서 N=8이고 [1,5,2,3,6,2,3,7] L이 3인 예시를 다시 보자.

우리는 덱에 pair<int,int>형태로 값을 저장할 것이다. 하나는 value를 하나는 index를 저장할 것이다.

초기에는 덱이 비어있다. 1번째 숫자부터 8번째 숫자까지 인덱스를 움직이며 최솟값을 출력해보자.

• 인덱스 1의 값은 1이다.  덱에 아무것도 없다. 1을 덱에 넣는다. (덱 : 1)
• 인덱스 2의 값은 5다. 덱에 1이 있지만 1이 빠지고나면 최솟값이 될 가능성이 있으니 덱에 넣는다.(덱 : 1 5)
• 인덱스 3의 값은 2다. 덱의 맨 끝에는 5가 있다. 덱 안에 2가 있는 이상 5가 출력될 가능성은 없다. 쓸모없는 값이므로 5를 빼고 2를 넣는다. (덱 : 1 2)
• 인덱스 4의 값은 3이다. 이제 L값에 따라 가장 오래된 데이터를 빼야한다. 덱의 맨 앞에있는 값의 index를 보고 맨 앞의 값을 빼준다. 그리고 2 뒤에 3을 넣는다. (덱 : 2 3)
• 인덱스 5의 값은 6이다. 덱의 맨 앞에 있는 index를 봤을때 아직 L값에 걸리지 않는다. 따라서 앞의 값을 뺄 필요없고 뒤의 값을 비교하여 덱에 넣는다. (덱 : 2 3 6)

이런식으로 반복하며 각각의 단계마다 덱의 front값을 출력해주면 해당범위 내에서 최솟값을 O(N)에 출력할 수 있다.

이 문제의 핵심은 출력될 가능성이 없는 값들을 덱에 넣지 않는 것이다.

덱의 맨 뒤에 있는 수가 새로 넣으려는 수보다 크다면 맨 뒤의 수는 덱에서 빠지기전까지 덱에 있더라도 절대로 출력될 가능성이 없는것이다. 그러므로 빼준다. 이러면 우리는 계속하여 최솟값의 후보들을 덱에 유지할 수 있고, 현재 index와 front값의 인덱스를 비교하여 L값에 만족하지 못하는것들을 빼주는 작업만 해주면 된다.

/*
	21.01.13
	BOJ 11003 : 최솟값 찾기 (https://www.acmicpc.net/problem/11003)
	자료구조 / 덱
*/
#include <bits/stdc++.h>
using namespace std;

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N, L;
	cin >> N >> L;

	deque <pair<int, int>> deq;

	for (int i = 1; i <= N; i++) {
		int n;
		cin >> n;

		if (!deq.empty() && deq.front().second <= i - L) {
			deq.pop_front();
		}

		while (!deq.empty() && deq.back().first > n) {
			deq.pop_back();
		}

		deq.push_back({n,i});
		cout << deq.front().first << " ";
	}



	return 0;
}