[BOJ P5][C++] 11003번: 최솟값 찾기

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

11003번: 최솟값 찾기

 

문제

N개의 수 A1, A2, ..., AN과 L이 주어진다.

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

입력

첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000)

둘째 줄에는 N개의 수 Ai가 주어진다. (-109 ≤ Ai ≤ 109)

출력

첫째 줄에 Di를 공백으로 구분하여 순서대로 출력한다.

 

풀이1 - 시간초과

(1)

덱에는 최대 l개 이하의 원소만 있을 수 있도록

새로운 수를 넣었는데 갯수초과라면 가장 오래된 애를 pop

 

(2)

그리고 최솟값을 구하면 되는데...

// Authored by : seondal
// Co-authored by : -

//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <deque>

using namespace std;

vector<int> v;
deque<int> d;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int n, l;
    cin >> n >> l;
    
    for(int i=0; i<n; i++){
        int tmp;
        cin >> tmp;
        v.push_back(tmp);
    }
    
    for(int i=0; i<n; i++){
        // (1)
        d.push_back(v[i]);
        if(d.size() > l) d.pop_front();
        
        // (2) 최솟값 구하기
        int min = 1000000001;
        for(int j=0; j<d.size(); j++){
            if(min > d[j]) min = d[j];
        }
        cout << min << " ";
    }
    
    
    return 0;
}

/*
 */

 

어림도없지~~ 역시 시간 초과에 걸렸다

 

---

 

풀이2 - 성공

 

시간 절약을 위해 덱의 기능을 이용해서 최솟값을 실시간으로 구해보자

 

우선 덱에 집어넣을때 {넣은 번째, 값} 의 쌍으로 집어넣기로 했다

deque<pair<int, int>> d;

그러면 덱의 사이즈가 아닌

d.front().first 값과 for문의 i값을 비교해서 빠져야 할 원소를 타이밍에 맞게 pop 이 가능하다

if(!d.empty() && i >= d.front().first + l) d.pop_front();

 

그러면 이제 덱의 사이즈를 신경쓰지 않고 그냥 pop해도 되는 상태가 만들어졌으니

이제 push를 하기 전에 자신보다 큰 원소는 빼버리는 작업을 진행

while(!d.empty() && d.back().second > v[i-1]) d.pop_back();

 

그러면 덱의 맨 얖은 해당 시점에서 최솟값인 애들만 front 에 있게 된다

그러면 그 최솟값인 front 를 출력해주면 간단 해결

 

// Authored by : seondal
// Co-authored by : -

//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <deque>

using namespace std;

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int n, l;
    cin >> n >> l;
    
    for(int i=1; i<=n; i++){
        int tmp;
        cin >> tmp;
        v.push_back(tmp);
    }
    
    for(int i=1; i<=n; i++){
        if(!d.empty() && i >= d.front().first + l) d.pop_front();
        while(!d.empty() && d.back().second > v[i-1]) d.pop_back();
        d.push_back({i, v[i-1]});
        cout << d.front().second << " ";
    }
    
    
    return 0;
}

/*
 */