최솟값 찾기 (feat. 백준, 11003번)

최솟값 찾기
https://www.acmicpc.net/problem/11003

11003번: 최솟값 찾기

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    deque<pair<int, int>> ans;
    register int N, L;
    cin >> N >> L;
    for(register int i = 1, v; i <= N; ++i){
        cin >> v;
        if(!ans.empty() && ans.front().second < i - L + 1)
            ans.pop_front();
        while(!ans.empty() && ans.back().first >= v)
            ans.pop_back();
        ans.push_back(make_pair(v, i));
        cout << ans.front().first << " ";
    }
	return 0;
}
// *&)*@*

 

반응형

해당 문제는 i - L + 1 ~ i 까지의 값을 가져가면서 그중 최소값을 찾는 것이 아니라, 최소값만 남기면서 그 값을 출력하는 것이 핵심입니다.