[백준][c++] 11003번: 최솟값 찾기

문제 해석

각 슬라이딩 윈도우 크기 내에서 최소값을 출력하는 문제입니다.

 

풀이

벡터와 덱을 이용해 해결했습니다.

• 각 D(i)에 대해 다음을 반복합니다.
  • 현재 추가되는 A(i)와 dq.back(덱에서 가장 큰 수)를 비교하여 A(i)가 더 작다면 dq.back을 pop함
  • A(i)를 인덱스와 함께 back에 추가
  • dq.front가 윈도우 크기를 벗어났다면 pop함
  • dq.front를 출력

 

코드

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

int main() {

    //입출력 최적화
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    //입력부
    int n,l;
    cin >> n >> l;
    vector<int> a(n);

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

    //해결부
    deque<pair<int, int>> dq; // {data, index}

    for(int i=0;i<n;i++){
        while (!dq.empty() && dq.back().first > a[i])
            dq.pop_back();

        dq.push_back({a[i],i});

        while (!dq.empty() && dq.front().second <= i-l)
            dq.pop_front();

        cout << dq.front().first<<' ';
    }

    return 0;
}