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

11003번: 최솟값 찾기

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

int numbers[5000001];
int n, l;

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 >> numbers[i];

    deque<pair<int, int> > list;

    for(int i = 0; i < n; i++){
        if(!list.empty() && list.front().second < i - l + 1)
            list.pop_front();

        while(!list.empty() && list.back().first > numbers[i]){
            list.pop_back();
        }
        
        list.push_back(make_pair(numbers[i], i));
        cout << list.front().first << " ";
    }
    cout << '\n';
}
/*
1 5 2 3 6 2 3 7 3 5 2 6

D(i) = A(i - l + 1) ~ A(i)
범위 = 윈도우가 l이란 뜻
*/

---

 이전 네트워크 수업에서 슬라이딩 윈도우 개념을 공부를 해서 쉬운 문제라고 생각을 했는데 처음 제출에서 시간 초과가 나서 당황을 한 문제였습니다. 생각을 해 보니 아래 코드가 문제였습니다.

        for(int j = 0; j < l; j++){
            if(!list.empty() && list.back().first > numbers[i])
                list.pop_back();
        }

 위 정답에서 while문 대신 제출했던 for문으로 역할은 슬라이딩 윈도우에서 뒷 부분을 빼는 부분이었습니다. 그런데 위 방법을 사용할 경우 l 길이만큼 무조건 탐색을 강제하기 때문에 시간초과가 나게 됩니다. (l이 500만까지 가능) 그래서 이를 while문으로 대체해 슬라이딩 윈도우에서 필요한 부분들만 빼기 때문에 연산을 줄여 시간초과를 피할 수 있었습니다.