백준 11003번 : 최솟값 찾기

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

11003번: 최솟값 찾기

 

 

 

 

 

 

L 길이 만큼 각 subarray에서 최솟값을 찾는 문제다. 당연한 소리지만 만약 모든경우를 탐색하는 즉 O(NL) 방법으로 이 문제를 풀면 시간초과가 뜰것이다. 그래서 매번 최소값을 찾기위한 연산이 필요없는 자료구조를 구현해야한다. 처음에는 항상 정렬된 상태를 가지는 우선순위 큐를 생각했다. 그런데 평범한 우선순위큐를 사용했을때 생기는 문제는, 만약 subarray가 가장 앞의 index를 벗어나면 가장 앞의 원소를 빼줘야하는데 우선순위큐는 이것을 O(1) 방법으로 할 수가 없다.

 그래서 생각한 방법은 디큐(데크)를 이용한 방법이다. 

subarray가 오른쪽으로 한칸씩 이동하면 새로원소를 디큐에 추가하는데, 이때 추가하기 전에 디큐의 뒤에있는 원소들이 새로 추가하는 원소보다 크면 큰 것들은 다 제거해주고 추가해준다. 왜냐하면 그것들은 최소값으로서 출력되는 일이 없기 때문이다.그러면 디큐에는 항상 오름차순의 배열이 저장되게 된다. 그리고 디큐의 앞부분 원소가 index가 만약 subarray의 index 범위를 벗어나면 제거해준다.

 

 

 위 그림이 이제 앞의 설명을 나타낸것인데, 여기서 보면 subarray가 옆으로 한칸 이동하면 2는 index가 범위를 벗어나니까 제거되고, 4와 5같은 경우 새로 추가되는 3보다 작으므로 제거된다. 즉 그러면 디큐에는 오름차순으로 값들이 저장되고 front를 리턴하면 최솟값을 항상 얻을 수  있다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <unordered_map>
#include <deque>

typedef long long ll;

using namespace std;
deque<pair<int,int>> dq;

int main(int argc, char** argv)
{	

	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int n, l;
	cin >> n >> l;


	
	for(int i=0; i<n; i++){
		int a;
		cin >> a;
		
		if(!dq.empty() && dq.front().second < i-l+1){
			dq.pop_front();
		}

		while(!dq.empty() && dq.back().first >= a){
			dq.pop_back();
		}

		dq.push_back(make_pair(a,i));
		
		cout << dq.front().first << ' ';
	}
	
	
	
}