Baekjoon 11003 최솟값 찾기

문제

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

걸린 시간

- 실패

시간 초과 풀이

C++

#include <stdio.h>
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm> // sort
#include <string.h> // memset
using namespace std;

#define INF 987654321

int main(){
    int N, L;
    scanf("%d %d", &N, &L);
    vector<int> A(N);
    for(int i = 0; i < N; i++)
        scanf("%d", &A[i]);
    // O(NL)
    deque<int> D;
    for(int i = 0; i < N; i++){ // O(N)
        // O(2)
        if(i > L)
            D.pop_front();
        D.push_back(A[i]);
        // O(L)
        printf("%d ", *min_element(D.begin(), D.end()));
    }
    return 0;
}

처음 작성한 코드는 선형 배열에 들어있는 값들 중에서 최소값을 찾아 출력하는 고지식한 방법으로, O(NL) 복잡도를 가져 시간초과가 난다.

덱을 단순히 부분 구간의 값을 저장하는 용도로 사용하는 것이 아닌, 최소값이 되는 후보들의 저장공간으로 쓰여야 한다.

옳은 풀이

C++

#include <stdio.h>
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm> // sort
#include <string.h> // memset
using namespace std;

#define INF 987654321

int N, L, tmp;
deque<pair<int, int>> d;

int main(){
    scanf("%d %d", &N, &L);
    for(int i = 0; i < N; i++){
        scanf("%d", &tmp);
        // 덱이 비어있지 않고 덱의 마지막 요소가 
        // 입력된 값보다 크다면 제거
        while(!d.empty() && d.back().first > tmp)
            d.pop_back();
        // 덱에 값을 추가
        d.push_back(make_pair(tmp, i));
        // 덱의 첫 요소 구간값이 
        // 현재 구간(i-L ~ i)에 속하지 않으면 제거
        while(d.front().second <= i-L)
            d.pop_front();
        // 덱의 첫 요소 값을 출력
        printf("%d ", d.front().first);
    }
    return 0;
}

덱에 맨 처음 요소는 항상 최소가 되도록 값을 저장한다. (첫번째 while 문, 다음 push_back 연산)

값과 함께 구간 값도 쌍으로 저장되는데 덱에서 최소값을 꺼내어 출력하기 전, 해당 구간에 속해있는지를 구간 값을 확인한 후 최소값을 출력한다. (두번째 while 문, 다음 출력문)

덱의 쓰임을 첫 풀이와 비교했을 때 다음과 같은 점이 다르다.

1. 구간의 모든 값이 아닌, 최소값이 될 후보값만을 저장.
2. 과거에 저장해 두었던 최소값이 다른 구간에서도 최소값으로 사용될 수 있음.

겉모습이 창문을 한쪽으로 밀어가며 문제를 해결해 나가는 것과 닮았다고 해서 슬라이딩 윈도우라 할 수 없다.

위 두가지 조건을 만족해야 슬라이딩 윈도우라 할 수 있다.

참고

• 맨땅에 코딩 - Baekjoon(백준) : 11003번 (최소값 찾기)