백준 11003번 - 최솟값 찾기

www.acmicpc.net/problem/11003

11003번: 최솟값 찾기

덱과 슬라이딩 윈도우 알고리즘을 사용하면 되는 문제였다.

 

해결방법은 다음과 같다.

 

• 하나의 덱에 최솟값에 대한 정보를 담고 있는다.
• 이때 이 덱의 크기는 최대 L까지 이다.
• 그리고 이 덱에는 최솟값들의 후보를 모두 가지고 있는다.
• 또한 이 덱은 오름차순 정렬이 되어 있다.

무슨 소리인가 할 수 있는데 천천히 살펴보면 생각보다 어렵지 않게 구현이 가능하다.

 

먼저 덱에 최솟값에 대한 정보를 담고 있는다는 말은

 

새로운 Ai를 입력받을 때마다 덱을 갱신시켜줘야 한다는 말이다.

 

덱을 deque <pair <int, int>> 로 선언을 하게 된다면 pair<값, index> 이렇게 생각할 수 있다.

 

따라서 덱이 오름차순 정렬되어있으므로(이것도 이따가 왜 그런지 설명하겠음) 

맨 앞, 즉 deque.front()가 더 이상 필요 없는 수라면 pop 해주면 된다.

 

필요 없다는 조건은 문제에서 나왔듯이 Ai-L+1 미만의 수들일 것이다.

이 조건은 index를 통해 알 수 있으므로 위와 같은 방법이 가능하다.

 

이렇게 Ai-L+1과 Ai까지의 수만을 담고 있을 거기 때문에 덱의 최대 크기는 L이 된다.

 

이제 어떻게 최솟값들의 후보를 모두 가지고 있을까?

 

예를 들어 현재 덱에는 2,3,4,5,6이 들어있고 새로 입력받는 수가 1이라고 해보자.

 

그렇다면 앞으로 1보다 작은 수가 들어오기 전까지는 무조건 1이 최솟값이 된다.

 

즉 현재 덱에 저장되어있는 2,3,4,5,6은 필요가 없어진다는 얘기다.

 

또 다른 예를 들어보자.

 

현재 덱에 1,2,4,5,6가 들어있고 새로 입력받는 수가 3이라고 가정해보자.

 

그렇다면 4,5,6은 전혀 쓸모가 없는 수가 돼버린다.

 

왜냐하면 가장 최근에 3이라는 최솟값이 들어왔으므로 4,5,6은 최솟값의 후보가 될 수 없다는 얘기다.

 

따라서 4,5,6을 pop 해주고 3을 집어넣은 1,2,3이 현재의 덱이 될 것이다.

 

이렇게 현재 입력받는 수보다 작은 것들은 최솟값의 후보가 될 수 없기에 모두 덱에서 pop 해주기 때문에 자연스럽게 오름차순 정렬이 완성된다.  

 

결국 정답은 매 index마다 덱의 맨 앞에 있는 수가 될 것이다.

 

코드에도 주석을 잘 달아놓았으니 이해하기 어렵진 않을 것 같다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n, l, x;
    cin >> n >> l;
    vector<int>ans;
    deque<pair<int, int>>dq; // pair< 값 , index >
    for (int i = 0; i < n; i++) {
        if (!dq.empty() && dq.front().second < i - l + 1) {
            dq.pop_front(); // 덱에는 무조건 Ai-L+1 ~ Ai까지의 원소만 있어야 함
        }
        cin >> x;
        while (!dq.empty() && dq.back().first > x) { // 최소값이 될 수 있는 후보들만 남기고 삭제
            dq.pop_back(); // 결국 이 과정에서 덱이 오름차순 정렬이 될 수 밖에 없음
        }
        dq.push_back(make_pair(x, i));
        ans.push_back(dq.front().first);
    }
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << " ";
    }
    cout << "\n";
}