[백준 / BOJ] C++ 11003 최솟값 찾기

11003번: 최솟값 찾기

 

문제

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

11003번: 최솟값 찾기

 

 

풀이

차례대로 수를 입력받아 최소 힙(우선순위 큐)에 추가한다. 가장 작은 숫자가 현재보다 L만큼 이전 범위 안의 수가 아닌 경우, 범위를 벗어나므로 pop 한다. 최솟값이 범위를 만족할 때 top 원소를 출력해 준다.

 

코드를 줄이고 줄여서 C++ 기준 숏코딩 1등도 했다.

 

(덱을 사용하는 풀이도 있다고 해서 공부한 후에 추가하겠다.)

 

코드

#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n, l, x;
  cin >> n >> l;
  priority_queue<pair<int, int>> pq;
  for (int i = 1; i <= n; i++) {
    cin >> x;
    pq.push({-x, i}); // 입력받은 수와 몇 번째 입력인지
    // 최솟값이 범위 안이 아니면
    while (pq.top().second <= i - l)
      pq.pop();
    cout << -pq.top().first << ' ';
  }
}