[BOJ / C++] 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

 

문제 풀이

이 문제 풀이 포스팅에 앞서, '모노토닉 큐' 라는 자료구조를 블로그에 정리한 글이 있다. 이것을 이용했다.

[자료구조] 모노토닉 큐 (Monotonic Queue)

 

이 문제는 'Do it! 알고리즘 코딩 테스트 C++ [개정판] : 코딩 테스트를 처음 경험하는 취준생의 필독서' 서적에서 '슬라이딩 윈도우' 파트에 소개된 난이도가 가장 어려운 문제였고, 여기서 모노토닉 큐를 활용해 슬라이딩 윈도우를 풀어내는 트릭을 알려주어서 풀게 된 문제다.

 

단순히 모노토닉 큐(단조 덱)를 이용만 하면 풀 수 있는 문제였기 때문에, 자세한 문제 풀이는 위의 모노토닉 큐에 대한 포스팅으로 갈음한다.

 

한가지 특이한 점이 있다면, 모노토닉 큐를 활용할 때에 덱의 원소로 주로 (인덱스, 값) 형태의 pair<T, T>를 사용하게 되는데, 여기서는 원본 배열을 유지한 채로 인덱스만 덱에 저장하는 방식으로 풀었다.

 

BOJ를 이용하며 난생 처음으로 시도해본 플래티넘 레벨의 문제여서 감회가 남다르다.

모노토닉 큐를 활용한 최댓값 / 최솟값 트릭 문제를 몇 개 더 풀어봐야겠다.

문제 풀이 코드

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, l;
    vector<int> a;
    deque<int> deq; //인덱스만 저장할거임

    cin >> n >> l;

    a.resize(n);

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

    for(int i = 1; i <= n; i++) {
        while(deq.size() && a[deq.back()] > a[i]) {
            deq.pop_back();
        }
        deq.push_back(i);

        if(deq.front() <= i - l) {
            deq.pop_front();
        }

        cout << a[deq.front()] << ' ';
    }

    return 0;
}