백준 11003번 최솟값 찾기 - 덱 정렬

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

 

아이디어:

1. 슬라이딩 윈도우라고 생각했을 때, 범위가 i - L + 1 부터 1까지 => 슬라이딩 윈도우의 사이즈가 L

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

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

4. 새 노드가 추가될 때, 덱에서 새 노드의 숫자보다 큰 숫자의 노드는 전부 삭제 (= 모노톤 스택)

5. 새 값 추가. 새 값은 무조건 추가된다.

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

 

덱의 정렬은 모노톤 스택과 동일한 방식이다.

 

pair 사용하는 정갈한 풀이

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, L, tmp;
	cin >> N >> L;
	deque<pair<int, int>> d;	

	for (int i = 0; i < N; i++) {
		cin >> tmp;

		while (!d.empty() && d.back().first > tmp) {
			d.pop_back();
		}

		d.push_back({ tmp, i });
		
		if (d.front().second <= i - L) {
			d.pop_front();
		}

		cout << d.front().first << " ";
	}

	return 0;

}

 

Node 사용하는 풀이

// 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;

}

 

덱으로 정렬하는 방법

 

사이즈가 L인 슬라이딩 윈도우

덱에 들어가는 자료형은 <long, long>을 갖는 Node (인덱스, 값을 의미)

 

(i)

현재 덱: (1, 1), (2, 5)

(3, 2)가 추가되는 상황

2보다 큰 값들은 모두 제거하며 2보다 작거나 같은 값을 만났을 때 멈추고 삽입

→ 이후 덱: (1, 1), (3, 2)

인덱스의 범위가 1~3이므로 슬라이딩 윈도우의 크기 3과 동일

 

(ii)

현재 덱: (1, 1), (3, 2)

(4, 3)이 추가되는 상황

3보다 큰 값들은 모두 제거하며 3보다 작거나 같은 값을 만났을 때 멈추고 삽입

→ 이후 덱: (1, 1), (3, 2), (4, 3)

그러나 인덱스의 범위가 1~4이므로 슬라이딩 윈도우의 크기 3보다 크다.

따라서 맨 앞의 노드를 삭제한다.

→ 이후 덱: (3, 2), (4, 3)

 

덱은 이런 과정으로 정렬된 오름차순을 유지한다.

최솟값은 덱의 가장 앞에 있는 노드이다.