[백준 11003] 최솟값 찾기 (C++)

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

11003번: 최솟값 찾기

1. 주의할 점

- TLE가 나지 않도록 한다

 

2. 구현

- 덱이나 우선순위큐를 사용하여 해결한다

- 모든 원소를 입력받을 때, 삽입을 수행한다

- 우선순위 큐의 크기가 Len만큼 길지 않다면, 출력만 수행한다

- 우선순위 큐의 크기가 Len보다 크거다 같다면, While문을 통해 우선순위큐에서 제거작업을 수행한다. 이때, Top에 존재하는 원소가 현재 검사하는 Len길이의 구간안에 존재한다면 While문을 종료한다

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
struct info {
	int idx, val;
};
struct cmp {
	bool operator()(info &a, info &b) {
		return a.val > b.val;
	}
};

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int num, len, val;
	cin >> num >> len;
	priority_queue<info,vector<info>,cmp> pq;
	for (int i = 0; i < num; i++) {
		cin >> val;
		pq.push({ i,val });
		if (pq.size() >= len) {
			while (!pq.empty()) {
				if (pq.top().idx + len <= i) pq.pop();
				else break;
			}
		}
		cout << pq.top().val << " ";
	}
	return 0;
}