[BOJ 11003번] 덱을 이용한 최솟값 문제

처음에 이문제를 보고 덱을 이용해서 원소를 앞뒤로 삭제 추가 해주면서

포인터를 이용해서 최솟값만 그때 그때 뽑아주면 된다고 생각했지만

최악의 경우 N은 1000000 인데 시간복잡도가 N^2logN 이 돼서 아무리 최적화 해봐도 통과되지 않았다.

 

일단 원소가 앞에서는 삭제되고 뒤에서는 추가 되니까 덱을 발상하는것을 어렵지 않았다.

그리고 한칸씩 슬라이딩 윈도우가 지나가면서 변하는 최솟값을 구하는것인데 이부분을 구현하기가 어려웠다.

그래서 답을 확인했고 이번에 덱의 활용법을 새로 배웠다.

 

일단 한칸씩 이동하기 때문에 덱 전체를 그때마다 sorting하는것은 너무 낭비라는것을 이해해야 한다.

이 부분에서 시간초과가 났다

 

이미 알고있는 원소를 충분히 활용하면서 최솟값을 찾아내는 방법은 덱의 성질을 이용하는 것이다.

덱은 앞부분이 항상 최솟값을 유지하도록 우선순위 큐처럼 활용할수 있다. 그리고 언제든지 앞의 원소를 삭제할수 있다.

관심있는것은 최솟값이기 때문에 현재 원소와 비교해서 최솟값이 될수 없는 의미없는 값들은 뒤에서부터 과감하게 pop을 해버리고

현재 원소를 덱에 알맞은 곳에 위치시켜준다. 이러면 언제나 덱 앞부분부터 최소 한개이상의 작은 값들이 순서대로 쌓이게 된다.

 

하지만 이때 주의할것이 덱의 앞부분은 한칸씩 없어진다는것이다.

그래서 현재 추가된 원소는 유효기간이 정해져 있다. 즉 슬라이딩 윈도우 사이즈만큼 살아 있을수 있고 이 기간이 지나면 pop을 해주는 코드를 추가해야한다. 현재 원소의 인덱스와 윈도우 사이즈를 통해서 구할수 있었다.

 

확실히 플래티넘 문제라서 여러 테크닉이 쓰였고 인덱스 포함/미포함등 헷갈리는 것도 있었다.

이런 스킬들은 나중에 비슷한 상황에서 아이디어를 발상하는데 도움이 될것같다.

 

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

deque<pair<int,int>> dq;
vector<int> v,d;

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

  int n,window;

  cin >> n >> window;

  for(int i=0; i<n; i++){
    int a;
    cin >> a;
    v.push_back(a);
  }

  for(int i=0; i<n; i++){
    // 덱의 현재 원소보다 큰값들은 의미가 없으므로 뒤에서부터 과감히 pop을 한다.
    while(!dq.empty() && dq.back().Y >= v[i]) dq.pop_back();
  
    // 그리고 덱에는 항상 현재 원소한개가 추가된다. 유효기간이 있기때문에 인덱스도 추가해준다,
    dq.push_back({i, v[i]});


    // 유효기간이 지난 원소는 앞에서 pop을 해줘야 한다.
    if(dq.front().first <= i-window) dq.pop_front();

    // 현재 윈도우에서 가장작은 값을 정답 배열에 추가한다.
    d.push_back(dq.front().second);

  
  }

  for(int i=0; i<n; i++){
    cout << d[i] << ' ';
  }

  
}