어흥

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

알고리즘/백준

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

라이언납시오 2021. 8. 20. 17:29
728x90
반응형

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

 

11003번: 최솟값 찾기

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

www.acmicpc.net

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;
}
728x90
반응형

'알고리즘 > 백준' 카테고리의 다른 글

[백준 2696] 중앙값 구하기 (C++)  (0) 2021.08.20
[백준 15903] 카드 합체 놀이 (C++)  (0) 2021.08.20
[백준 10986] 나머지 합 (C++)  (3) 2021.08.18
[백준 2800] 괄호 제거 (C++)  (0) 2021.08.07
[백준 12904] A와 B (C++)  (0) 2021.08.07
Comments