[백준] 11003: 최솟값 찾기

0. 문제 주소

 

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

11003번: 최솟값 찾기

 

 

1. 풀이

 

인덱스 트리를 이용하여 풀어보려고도 했는데,,, 재귀로 하면 TLE가 난다.

비재귀 세그 트리를 써야 한다는데 나중에 알아봐야겠다.

 

도저히 모르겠어서 찾아본 결과 deque을 이용한 O(N) 풀이를 찾았다.

 

슬라이딩 윈도우 기법을 사용하되, 가지고 갈 필요가 없는 원소들은 바로바로 빼 줄 것이다.

 

0. pair를 이용하여 각 원소에 순서를 붙여준다.

1. 덱이 비어 있다면 이번 원소를 push_back한다.

2. 덱이 비어 있지 않다면,

  2-1. 덱의 맨 앞부터, empty 여부를 확인하며 pair로 같이 저장한 index를 이용해

  이번 윈도우에서 있으면 안 될 원소를 빼준다.

  2-2. 덱의 맨 뒤부터, 이번에 새로 들어올 원소보다 큰 원소들은 빼준다. 역시 empty 여부는 확인한다.

  이번에 새로 들어올 원소는 덱에 이미 있는 원소들보다 더 오래 있으므로, 이러한 원소들은 덱에 있을 필요가 없다.

  2-3. 덱의 맨 뒤에 새로 들어올 원소를 넣는다.

3. 맨 앞에 위치한 원소가 이번 구간에서의 최솟값이다.

 

 

2. 풀이 코드

 

* 유의할 점

 

 

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

#define pii pair<int, int>

using namespace std;

int N, L, a;
deque<pii> dq;


int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif // ONLINE_JUDGE
    
    scanf("%d %d", &N, &L);
    for (int i=1;i<=N;i++){
        scanf("%d", &a);
        while(dq.size() && dq.front().first <= i - L) {
            dq.pop_front();
        }
        
        while(dq.size() && dq.back().second >= a) {
            dq.pop_back();
        }
        dq.push_back(pii(i, a));
        
        printf("%d ", dq.front().second);
    }

    return 0;
}