[백준]11003_최솟값 찾기

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

Solved

✔ 자료구조 / 우선순위 큐/ 덱(deque)
✔ 플래티넘 문제. SDS 특강 풀이를 복기해보자.
✔ 데이터 세팅: 배열의 길이는 5백만이다. 즉, 여러번 볼 시간 없으니 입력과 동시에 무언가 처리를 해야 문제를 시간 내에 풀 수 있을 것이다.
✔ 플래티넘 문제치고 풀이는 짧다.배열의 시작과 끝의 데이터 삽입/삭제가 자유로운 덱의 특성을 살려 지금 들어온 값이 앞에 들어온 값보다 크면 아예 덱에 넣지 말자,
그리고 index==i-L이 되었을 때 덱의 첫번째 값을 pop하자,
그럼 자연스레 오름차순인 동시에 A(i-L+1)~A(i)의 값만 넣은 덱이 될 것이다.

using namespace std;
#include <iostream>
#include <deque>

int n, l, a;
deque<pair<int, int>> q;
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> l;
	for (int i = 0; i < n; i++) {
		cin >> a;
		while (!q.empty()) { //q가 비어있지 않으면
			pair<int, int> t = q.back(); //가장 마지막에 덜어온 값이
			if (t.second >= a) q.pop_back(); //이번 값보다 크면 없애기
			else break;//아니라면 스루해
		}
		q.push_back(make_pair(i, a));//들어온 차례, 이번에 들어온 값 넣기
		pair<int, int> t = q.front();//q에 있는 값중 가장 먼저 들어온값
		if (t.first == i - l) q.pop_front(), t = q.front();//이번 차례 포용 범위 밖이라면 pop. t 업데이트
		cout << t.second << ' ';
	}
}