백준 11003: 최솟값 찾기

문제 요약

N개의 수 A1, A2, ..., AN과 L이 주어진다.

Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.

문제 분류

• 자료 구조
• 우선순위 큐
• 덱

문제 풀이

우선순위 큐를 이용하여 해결하였다. 처음부터 입력을 받으며 우선순위 큐에 해당 값과 인덱스를 넣고, 오름차순으로 만든다.
이제 q.top()을 출력하면 되는데, 해당 값이 현재 인덱스 범위 내인지(q.top().second <= i - l)만 확인하면 된다.

이에 O(nlogn)의 복잡도로 해결할 수 있다.

이렇게 보니 참 쉬운 문제인데, 너무 어렵게 접근해서 오래걸린 것 같다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int main()
{
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;

	int n, l, input;

	cin >> n >> l;
	for (int i = 0; i < n; i++) {
		scanf("%d", &input);
		q.push({ input , i });

		auto t = q.top();
		while (q.top().second <= i - l) q.pop();
		printf("%d ", q.top());
	}
}