[C/C++] 백준 11003번 - 최솟값 찾기

백준 11003번 최솟값 찾기

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

11003번: 최솟값 찾기

 

    ● N과 L이 5,000,000이하 이므로 일반적으로 O(nlogn)의 시간복잡도를 가지는 정렬 알고리즘을 사용할 수 없음 

    ● O(n)의 시간 복잡도로 해결해야 하므로 슬라이싱 윈도우를 덱으로 구현하기

    ● 덱의 마지막 위치에서부터 now보다 큰 값은 덱에서 제거

    ● 덱의 마지막 위치에 now값 저장   

    ● 덱의 첫 번째 위치에서부터 L의 범위를 벗어난 값(now index - L <= index)을 덱에서 제거

 

#include<iostream>
#include<deque>
using namespace std;
typedef pair<int, int>Node;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, L;
	cin >> N >> L;
	deque<Node>mydeque;
	
	for (int i = 0; i < N; i++) {

		int now;
		cin >> now;

		while (mydeque.size() && mydeque.back().first > now) {
			mydeque.pop_back();
		}
		
		mydeque.push_back(Node(now, i));

		if (mydeque.front().second <= i - L) {
			mydeque.pop_front();
		}
		
		cout << mydeque.front().first << ' ';
	}	
}