C++ - 백준 11003 최솟값 찾기

/* 백준 11003 최솟값 찾기

* 문제

N개의 수 A1, A2, ..., AN과 L이 주어진다.
Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오.
이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.

* 입력

첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000)
둘째 줄에는 N개의 수 Ai가 주어진다. (-109 ≤ Ai ≤ 109)

* 출력

첫째 줄에 Di를 공백으로 구분하여 순서대로 출력한다.

* 예제 입력 1

12 3
1 5 2 3 6 2 3 7 3 5 2 6

* 예제 출력 1

1 1 1 2 2 2 2 2 3 3 2 2

*/

/* 풀이

    N = 12, L = 3

    Ai (i = 1 ~ N)
    ----------------------------------------
    i    1  2  3  4  5  6  7  8  9  10 11 12
    ----------------------------------------
    Ai   1  5  2  3  6  2  3  7  3  5  2  6

    Di (i = 1 ~ N)
    i   범위 (i<=0 => Ai 무시)   Di
    ------------------------------
    1   1-3+1 ~ 1  A1 ~ A1      1
    2   2-3+1 ~ 2  A1 ~ A2      1
    3   3-3+1 ~ 3  A1 ~ A3      1
    4   4-3+1 ~ 4  A2 ~ A4      2
    5   5-3+1 ~ 5  A3 ~ A5      2
    6   6-3+1 ~ 6  A4 ~ A6      2
    7              A5 ~ A7      2
    8              A6 ~ A8      2
    9              A7 ~ A9      3
    10             A8 ~ A10     3
    11             A9 ~ A11     2
    12             A10~ A12     2

일단 입출력 개수가 상당히 크기 때문에 cin과 stdio의 sync는 끊는다

    cin.tie(nullptr)->sync_with_stdio(false);

deque 에 최소값을 유지하도록 설계하면 될 것 같다.

    i       1  2  3  4  5  6  7  8  9  10 11 12
    a[i]    1  5  2  3  6  2  3  7  3  5  2  6
    -------------------------------------------

    1  deq  {{1, 1}}            처음은 deque가 비어 있으므로 push 한다, 1 을 출력
    5  deq  {{1, 1}, {5 ,2}}    1 은 5 보다 작으므로 그대로 push, 1 을 출력
    2  deq  {{1, 1}, {2, 3}}    5 는 2 보다 크므로 pop 해버리고 2 를 push, 1 을 출력
    3  deq  {{2, 3}, {3, 4}}    {1, 1} 은 이제 l 의 범위를 벗어 났으므로 pop
                                2 는 3 보다 작으므로 그냥 push, 2 를 출력
    6  deq  {{2, 3}, {3, 4}, {6, 5}}  3 < 6 이므로 그대로 push, 2 를 출력
    3  deq  {{2, 6}}            {2, 3} 은 범위를 벗어 낫으므로 pop,
                                3 과 6 은 2 보다 크므로 pop, 2 를 출력
    ...

*/

#include <iostream>
#include <vector>
#include <deque>

using std::cin, std::cout, std::vector, std::pair, std::deque;

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);

	int n, l;
	cin >> n >> l;

	vector<int> a(n + 1, 0);
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}

    // pair.first = a[i], pair.secon = i 저장장
	deque<pair<int, int>> deq;
	for (int i = 1; i <= n; ++i) {
        if (!deq.empty() && i == deq.front().second + l)
			deq.pop_front();
        while (!deq.empty() && deq.back().first > a[i])
			deq.pop_back();

		deq.push_back({a[i], i});
		cout << deq.front().first << ' ';
	}
	cout << '\n';
}