[백준 11003번] 최솟값 찾기

[백준 11003번] 최솟값 찾기

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를 공백으로 구분하여 순서대로 출력한다.

 

 

 풀이

#include <iostream>
#include <queue>
using namespace std;
struct cmp{
	bool operator()(pair<int, int> &a, pair<int, int> &b){
		if(a.first == b.first) return a.second < b.second;
		return a.first > b.first;
	}
};
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int N, L; cin >> N >> L;
	priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> q;
	for(int i=0;i<N;i++){
		int a; cin >> a;
		q.push(make_pair(a, i));
		while(q.top().second <= i - L) q.pop();
		cout << q.top().first << ' ';
	}
	return 0;
}

우선순위 큐를 활용하여 문제를 풀었다. 큐의 top에 가장 작은 값이 나오도록 유지하면서, L의 범위에 벗어나게 되면 pop해주면 된다. 덱으로도 풀 수 있다는데 생각보다 쉽게 풀렸다. 물플레 문제라고 해서 풀어봤는데 경험치 파밍문제였다.