어흥
[백준 11003] 최솟값 찾기 (C++) 본문
728x90
반응형
문제 링크: https://www.acmicpc.net/problem/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;
}
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