[알고리즘] 백준 11003 최솟값 찾기 // 슬라이딩 윈도우, 덱

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

* 완전탐색

• N개 숫자에대해 앞의 L 개 탐색 -> O(NL) -> 불가
• N이 500만이므로, 1번의 탐색만으로 끝내야함!

 

* 행동영역

• 슬라이딩 윈도우에서 덱을 활용하라.
• 나보다 큰값을 pop 반복으로 완탐,정렬 효과를 만들어라.

 

* 풀이

• 삽입하기전, 우측부터 비교 
• 크면 pop 반복 => 완탐효과, 정렬효과, 좌측이 최소값 효과!!
• 작으면 통과
• push data
• 좌측이 윈도우를 넘어가면 삭제 (인덱스 비교)
• 좌측(최소값) 출력

 

* 전체코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll n, L;
ll arr[5000000 + 4];
deque<pair<ll,ll>> d; // <idx, val>

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> L;

    for (int i = 0; i < n; ++i) {
        ll tmp;
        cin >> tmp;
        arr[i] = tmp;
    }
    d.push_back({ 0,arr[0] });
    cout << arr[0] << " ";

    
    for (int i = 1; i < n; ++i) {
        // 우측에서 삽입, 넣을때 자신보다 큰값은 삭제 => 좌측값이 최소값으로 유지되는 정렬효과
        // 하나씩빼기 => 완탐효과
        while (d.size() && d.back().second > arr[i]) {
            d.pop_back();
        }
        d.push_back({ i,arr[i] });
        
        // 좌측에서 제거할지 판단. 현재 idx - L <= 좌측idx -> L범위밖 -> 삭제
        if (d.front().first <= i - L) {
            d.pop_front();
        }

        // 좌측의 val == 최소값 출력
        cout << d.front().second << " ";
    }
    return 0;
}