BOJ 11003번 최소값 찾기

문제 링크

\(1 <= L <= N <= 5 \times 10^6\)

\(-10^9 <= A_i <= 10^9\)

정수 N과 L 이 주어지고 N개의 정수가 주어진다.

Di = Ai-L+1 ~ Ai 중의 최소값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이 때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.

O(N^2) 보다 빠른 가장 간단한 방법은 아마 multiset 같은걸로 O(NlgN) 에 구현하는 것일 것이다.

그런데 제한 상 시간이 넉넉하지가 않다. 이 문제는 덱을 사용하여 O(N) 에 풀 수가 있다.

어떻게 할까? 덱에는 인덱스가 들어간다. 덱은 무조건 앞에서 뒤로 갈수록 해당 인덱스에 존재하는 값이

커지는 형태로 정렬된 상태를 유지한다. 방법은 간단하다 매 순간마다 무조건 두가지만 해주면 된다.

1. 앞에서부터 사용할 수 없는 놈들을 빼준다.

2. 뒤에서부터 쓸모없는 놈들을 빼준다.

1번에서 사용할 수 없는 놈들이란 인덱스가 현재인덱스에서 L보다 멀리 떨어져있는 놈들을 뺀다는 것이다.

어차피 이 녀석들은 답에 쓰일 수 없는 녀석들이기 때문에 빼주는 것은 당연하다.

2번에서 쓸모없는 놈들이란 현재 보고있는 값보다 크기 때문에 어차피 답이 될 가능성이 없는 녀석들이다.

어차피 이번에 넣어줄 놈만 있으면 그보다 큰놈은 다 필요없어지기 때문에 빼도 상관없다.

2번 동작으로 무조건 덱안에 있는 인덱스들은 가리키는 값이 오름차순이 되게 한다.

1번 동작은 L 조건을 만족시켜주기 위하여 해주는 것이다.

이렇게 하면 당연히 매 순간마다 맨 앞에 있는 인덱스가 가리키는 값이 답이된다.

각 원소는 최대 한번씩 들어오고, 최대 한번씩나가기 때문에 시간복잡도는 O(N)이 된다.

#include <bits/stdc++.h>
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define fastio() ios_base::sync_with_stdio(false),cin.tie(NULL)
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int inf = 0x3c3c3c3c;
const long long infl = 0x3c3c3c3c3c3c3c3c;
 
int N, L, a;
deque<int> dq;
int A[5000003];
int main() {
    fastio();
    cin >> N >> L;
    for(int i = 0 ; i < N; i++){
        cin >> A[i];
        while(!dq.empty() && dq.front() <= i - L) dq.pop_front();
        while(!dq.empty() && A[dq.back()] >= A[i]) dq.pop_back();
        dq.push_back(i);
        cout << A[dq.front()] << ' ';
    }
    return 0;
}