[BOJ] 11003 : 최솟값 찾기 - travelbeeee

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

---

[ 알고리즘풀이 ]

 처음에는 세그트리를 이용하는 문제가 아닐까 고민하다가 Deque(덱)을 이용하면 된다는 것을 뒤늦게 캐치했다.

 Deque에는 < value, index > 를 저장하는데 Deque의 front 에는 현재 범위에서 가장 작은 값을 저장해 나갈 것이다.

1) 현재 가장 작은 값인 front 의 index가 범위 밖이라면 pop_front 를 진행한다.

2) 새로 들어온 값을 Deque의 back 부터 순회하며 새로 들어온 값보다 큰 값들은 새로 들어온 값에 의해 의미가 없어지므로 다 pop_back 을 진행한다. 

3) 새로 들어온 값을 push_back 해준다.

4) 2), 3)의 과정에 의해 Deque의 front 에는 범위 안에 있으면서 가장 작은 값이 오게된다. 따라서, Deque의 front 값을 출력해준다.

#include<iostream>
#include<deque>

using namespace std;

int N, L, x;
deque<pair<int, int>> list;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N >> L;
	for (int i = 0; i < N; i++) {
		cin >> x;
		if (!list.empty() && list.front().second <= (i - L))
			list.pop_front();

		while (!list.empty() && list.back().first >= x)
			list.pop_back();

		list.push_back({ x, i });
		cout << list.front().first << ' ';
	}

	return 0;
}

---