C++ / 백준 / 11003 / 최솟값 찾기

문제

 

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

11003번: 최솟값 찾기

문제풀이

 

다른 글을 보니 덱으로도 풀 수 있다고는 하는데 우선순위 큐로 풀었다.

이게 되나 싶었는데 통과가 됐다.

 

1부터 N까지 입력을 받으면서 idx-L+1번 숫자부터 현재 인덱스의 숫자까지 중에서 최솟값을 출력하기만 하면 된다.

우선순위큐를 이용해 항상 오름차순으로 정렬을 하도록 한다.

우선순위큐의 top부분의 인덱스가 필요한 부분의 인덱스가 아니라면 pop을 한다.

필요한 부분의 인덱스라면 break 하여 반복문을 탈출하고 해당 인덱스의 값을 출력하면 된다.

 

코드

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

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

	int N(0), L(0);
	cin >> N >> L;
	vector<int>nums(N, 0);
	
	priority_queue<pii, vector<pii>, greater<pii>>pq;
	for (int idx = 0; idx < N; ++idx) {
		cin >> nums[idx];
		pq.push({ nums[idx],idx });
		if (idx == 0) {			
			cout << nums[idx] << " ";
		}
		else {			
			while (1) {
				if (pq.top().second < idx - L + 1) pq.pop();
				else break;
			}
			cout << pq.top().first <<' ';
		}		
	}	
}