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

문제

11003번: 최솟값 찾기 (acmicpc.net)

11003번: 최솟값 찾기

 

풀이

저번에 풀어본 [백준] 15678 - 연세워터파크 (C++) — 6R33N 에 이어서 또다른 덱 활용 문제입니다.

이번 문제는 주어진 수열에서, L 크기의 구간에서 지속적으로 최솟값을 찾아야 하는 문제입니다.

 

A가 2 1 5 4 2, L이 3인 경우를 예로 들어보겠습니다.

먼저 dq에 첫번째 숫자가 들어가므로 2가 저장됩니다. (2)

1이 들어오는데, 2보다 작으므로 2를 제거하고 1을 저장합니다. (1)

5가 들어오는데, 1보다 크므로 일단 저장합니다. (1, 5)

4가 들어오는데, 5보다 작으므로 5를 제거하고 4를 저장합니다. (1, 4)

L이 3이므로 1을 제거합니다. 2가 들어오는데, 4보다 작으므로 4를 제거하고 2를 저장합니다. (2)

2 1 1 1, 덱의 첫번째 원소가 해당 구간(L)의 최솟값이 되게 됩니다.

 

결론적으로, 위 과정을 반복하면 min 함수를 사용하지 않고도 최솟값을 구할 수 있게 됩니다.

#include <deque>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  
  int N, L;
  cin >> N >> L;

  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }

  deque<pair<int, int>> dq;
  for (int i = 0; i < N; i++) {
    if (!dq.empty() && i == dq.front().second + L) {
      dq.pop_front();
    }

    while (!dq.empty() && dq.back().first > A[i]) {
      dq.pop_back();
    }

    dq.push_back({A[i], i});
    cout << dq.front().first << " ";
  }
    
  return 0;
}