백준 11003 최솟값 찾기

deque를 선언하고 다음을 구현한다

0. x를 읽는다

1. 디큐가 비어있으면 x를 디큐에 넣는다.

2. 디큐의 front가 슬라이딩윈도우를 벗어나는 값일 경우 디큐에서 뺀다.

즉 디큐의 front값의 index와 현재 탐색하는 index의 거리가 윈도우의 사이즈보다 클 경우 디큐에서 뺀다

3. 디큐의 back값의 value가 현재 탐색하는 value보다 크거나 같을 경우 디큐에서 뺀다.

4. 디큐의 back값의 value가 현재 탐색하는 value보다 작을때 까지 3번을 반복한다

여기서 2번은 쉽게 이해가 되고,

3번을 보자.

만약 디큐에 x라는 값이 들어갔다고 하자,

이때 디큐 내부에서 x보다 큰 값은 필요가 없어진다.

근거는 다음과 같다.

1. 만약 윈도우에 남아 있으면서, x보다 큰 값을 y라고 하자.

2. 그런데 y는 x보다 먼저 들어온 값이다. 따라서 y는 x보다 먼저 윈도우를 빠져 나간다.

3. 즉, x는 y보다 오래 살아있으므로 x보다 큰 y를 쓸 일이 없다. 쓸거면 x를 썼지.

4. 따라서 y는 필요 없다.

4번을 보자.

만약 디큐에 x보다 작은 값을 back에서 발견했다. 그럼 3번을 반복하는 루프를 끝내도 된다.

그 근거는 다음과 같다.

다음과 같은 예를 생각하자

디큐 : 1, 7, 2, 3, 5

x : 3

이때, 3번과 4번과정을 진행하며 디큐는 [1,7,2]가 될것이다.

그런데 이러한 형태의 디큐는 모순이다. 왜냐하면 7은 2가 들어올 때 진작에 빠졌을 것이기 때문이다.

따라서 위와 같은 예는 일어날 일 없으며, x보다 작은 값을 발견하는 즉시 루프를 끝내도 된다.

따라서 다음과 같은 코드가 만들어진다.

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>
#include <deque>

using namespace std;

deque<pair<int,int>> sldWndw; //first = index, second = value
int N, WndwSize;

int main() {
	scanf("%d %d", &N, &WndwSize);

	int temp;
	for (int i = 0; i < N; i++) {
		scanf("%d", &temp);
		if (sldWndw.empty()) {
			sldWndw.push_back(make_pair(i, temp));
			printf("%d ", temp);
		}
		else {
			if (!sldWndw.empty()) {
				if (i - WndwSize >= sldWndw.front().first ) {
					sldWndw.pop_front();
				}
			}
			while (true) {
				if (sldWndw.empty() || sldWndw.back().second < temp) break;
				sldWndw.pop_back();
			}
			sldWndw.push_back(make_pair(i, temp));
			printf("%d ", sldWndw.front().second);
		}
	}
	return 0;
}