[BOJ/C++] 11003 최솟값 찾기

슬라이딩 윈도우 알고리즘을 통해 문제를 해결할 수 있습니다.

최솟값의 범위가 $i-L+1$ 부터 $i$까지 이므로 범위는 $L$ 입니다.

N과 L의 범위가 5,000,000 이기 때문에 정렬을 사용할 수 없으므로 Deque를 이용해볼 수 있습니다.

• Deque에 인덱스와 숫자 형태로 저장합니다.
• 이후 뒤에서부터 비교하여 새 노드보다 값이 크다면 노드를 삭제합니다.
• 이때 덱의 인덱스 범위는 1~3으로 슬라이딩 윈도우의 크기와 같습니다.
• 이때 최솟값은 덱의 맨 앞에있는 요소인 1입니다.

• 마지막 인덱스 - 슬라이딩 윈도우 크기가 초과되므로 맨 앞 노드를 삭제합니다

• Deque와 결과는 위처럼 동작합니다

// boj p5 11003
// 최솟값 찾기

#include <iostream>
#include <deque>

using namespace std;


int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int N, L;
	deque<pair<int, int>> dq;
	cin >> N >> L;

	for (int k = 0; k < N; k++)
	{
		int tmp;
		cin >> tmp;
		
		while (dq.size() && dq.back().second > tmp)
			dq.pop_back();

		dq.push_back(make_pair(k, tmp));
		if (dq.front().first <= k - L)
			dq.pop_front();

		cout << dq.front().second << ' ' ;
	}
	

	return 0;
}