[백준 11003] 최솟값 찾기(C++)

최솟값 찾기

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

문제

문제 접근

• 문제의 흐름을 예제를 통해 살펴보자.

• 가장 직관 적인 방식으로는 요소를 순서대로 주어진 길이만큼 보며 그때그때 정렬하여 최솟값을 구할 수 있다.

시간 제한은 2.4초이고 수열의 크기와 길이는 5,000,000개 제한이다. N개의 범위에 대해서 정렬을하면 LlogL의 시간복잡도를 가질 것이므로, NLlogL의 최악의 경우는 N과 L이 각각 5백만일 경우 NL만 계산해도 25조 이다.

어떻게든 시간복잡도를 줄일 수 있는 방법을 찾아야 한다.

 

자료구조를 적절히 사용하여 해당 구간의 최솟값을 구해야 한다.

먼저 deque을 사용하는 문제라는 것을 이미 알고 있었기 때문에 front와 back에서 일어나는 연산을 통해 deque이 정렬된 상태를 유지할 수 있도록 궁리를 했다.

 

결국 해당 문제에 대한 정보를 검색하고 나서야 이해할 수 있었다.

풀이 힌트

• Deque을 사용하기 위한 기본적인 컨셉
  • Deque이 정렬된 상태를 가져야 한다.
  • 최솟값은 Deque의 front에서 찾을 수 있다.
  • Deque에는 언제나 유효한 값만 들어있다.
• Deque을 정렬시키는 방법 (핵심)
  • 덱이 정렬되어 있기 때문에 Front에서 최솟값을 찾을 수 있다.
  • Back에서는 최솟값을 가질 수 있는 값들을 갱신해준다: 유효성의 길이가 길고, 덱의 후미에 있는 값보다 작으니, 자신이 들어옴으로써 의미가 없어지는 덱의 후미를 모두 pop해준다.
  • 덱의 요소가 {3, 5, 8}일 때 4를 삽입하는 예를 들어보자.
    • 4를 뒤에서부터 삽입하려고 한다.
    • 삽입하려는 값이 back(8) 보다 작기 때문에 8을 뽑아준다. {3, 5}
    • 삽입하려는 값이 back(5) 보다 작기 때문에 5를 뽑아준다. {3}
    • 삽입하려는 값이 back(3) 보다 크기 때문에 4를 삽입한다. {3, 4}
• 이제, Deque을 이용하여 문제를 해결하는 과정을 따라가 보자.

 

이런 식으로 덱을 정렬된 상태와 유효한 상태를 유지하면서 최솟값을 찾는다.

 

코드

• 덱에 요소가 순서대로 들어가고 있으며, 값을 하나씩 살펴보기 때문에 현재 인덱스에서 Deque의 front 값의 유효성만 따지는 것으로 충분하다.

if (!D.empty() && D.front().second + L <= i) {
    D.pop_front();
}

• 전체 코드

#include <iostream>
#include <algorithm>
#include <deque>

using namespace std;
deque<pair<int, int> > D;
int input[5000010];

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

    int N, L;
    cin >> N >> L;

    for (int i = 0; i < N; ++i) {
        cin >> input[i];
    }
    for (int i = 0; i < N; ++i) {
        // index 순서대로 뒤로 삽입한다. == 앞에 있는 원소가 가장 오래된 원소
        // 가장 앞에 있는 원소를 제거할 때 해당 인덱스가 유효 범위를 벗어나는 즉시 제거된다.
        // 값과 등장한 순서가 오름차순으로 정렬이 되어있기 때문에 가능하다.
        if (!D.empty() && D.front().second + L <= i) {
            D.pop_front();
        }
        /**
         * 비교할 값보다 큰 요소를 삭제하고 자신으로 대체
         */
        while (!D.empty() && D.back().first >= input[i])
            D.pop_back();
        D.push_back({input[i], i});
        cout << D.front().first << " ";
    }
}

※ 오류나 개선점이 있다면 알려주세요 :) 신속히 수정하겠습니다.