백준 11003번 최솟값 찾기

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

 

아이디어:

1. 슬라이딩 윈도우 사용

2. 범위가 i - L + 1 부터 1까지 => 슬라이딩 윈도우의 사이즈가 L

3. 덱을 사용해서 덱 내부 정렬하듯이 구현

4. (값, 인덱스)로 구성된 Node 사용

5. 새 노드가 추가될 때, 덱에서 새 노드의 숫자보다 큰 숫자의 노드는 전부 삭제

6. 새 값 추가

7. 덱 안에 있는 노드의 인덱스 범위가 슬라이딩 윈도우의 크기를 벗어나면 (ex. L = 4인데, 덱에 있는 인덱스는 2~6인 경우) 덱의 앞에서부터 노드 제거

 

// 11003

#include <iostream>
#include <deque>

using namespace std;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	long N, L, k;
	typedef pair<long, long> Node; // Node with 2 long types (Value, Index)
	deque<Node> mydeque;

	cin >> N >> L;

	for (int i = 0; i < N; i++) {
		cin >> k; // now key

		while (mydeque.size() && mydeque.back().first > k) { // delete all the Nodes of which its value is lower than now key
			mydeque.pop_back();
		}

		mydeque.push_back(Node(k, i)); // add now key with its index and the deque is sorted automatically

		if (mydeque.front().second <= i - L) { // if the remain deque size is bigger than L (sliding window)
			mydeque.pop_front();	// delete the first node
		}

		cout << mydeque.front().first << " "; // print the first node
	}

	return 0;

}