[백준 C++] 11003 최솟값 찾기 - 우선순위큐

11003번: 최솟값 찾기

#include <iostream>
#include <queue>
using namespace std;

typedef pair<int, int> p;

int Seq[5000000];
priority_queue<p, vector<p>, greater<p>> PQ;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	int N, L;
	cin >> N >> L;
	for (int i = 0; i < N; ++i)
	{
		int Num;
		cin >> Num;
		Seq[i] = Num;
		PQ.emplace(Num, i);

		while (i - PQ.top().second >= L)
		{
			PQ.pop();
		}

		cout << PQ.top().first << ' ';
	}
}

---

 

우선순위 큐를 이용해서 푸는 문제입니다.

 

첫 번째 수부터 N 번째 수까지 순차적으로 입력받으면서

우선순위 큐(최소힙)에 인덱스 번호와 함께 값을 넣어줍니다.

 

매 인덱스 마다 큐에 저장된 최소값을 출력하되,

최소값의 인덱스와 현재 인덱스의 차이가 L 범위를 벗어날 경우에

L 범위 내의 최소값이 나타날때까지 해당 값들을 큐에서 제거해주어야 합니다.