[BOJ] 11003: 최솟값 찾기

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

 

 

 

 

#include <bits/stdc++.h>
using namespace std;
deque<pair<int, int>> dq;

int n, l, num;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> l;
  for (int i = 0; i < n; i++) {
    cin >> num;
    if (!dq.empty() && dq.front().second + l == i) dq.pop_front();
    while (!dq.empty() && dq.back().first >= num) dq.pop_back();
    dq.push_back({num, i});
    cout << dq.front().first << ' ';
  }
}

덱을 사용해서 해결할 수 있는 문제다.

 

덱에 각 구간의 최솟값을 저장해야 한다.

front는 항상 현재 구간의 최솟값이고 그 뒤에 오는 값들은 다음 구간의 최솟값이 될 수 있는 후보들이라고 생각하면 된다.

 

가장 먼저 해야할 것은 덱의 front 값이 현재 구간에서 유효한 값인지 알아야 한다.

그러기 위해 덱은 숫자뿐만 아니라 위치값까지도 가지고 있어야 한다.

따라서 탑에서 풀었던 것처럼 pair를 사용했다.

=> pair<숫자, 위치>

 

dq.front에 있는 숫자의 위치값에 L을 더한 값이 현재 구간의 끝이라는 건

이제 막 front가 유효한 구간을 벗어났다는 의미이므로 dq.pop_front()를 한다.

 

구간을 벗어난 숫자를 버린 후에는 새로운 숫자를 받아야 하는데,

덱의 back에서부터 대소를 비교해서 num이 더 작은 동안에 back을 pop해야한다.

=> 최솟값을 덱에 저장하기 위함이며 큰 값들은 이미 최솟값의 의미를 잃었기 때문에 pop해도 된다.

 

그 후 num과 해당 숫자의 위치를 함께 back에 push해야 하는데, num이 front보다 클 수도 있다.

이때 num이 front보다 크더라도 항상 push해야 하는 이유는

현재 구간에서 최솟값이 아니더라도 이후 구간에서 최솟값이 될 가능성이 있기 때문이다.

 

위 연산이 끝나면 dq.front()에는 해당 구간의 최솟값이 들어있기 때문에 front를 출력하면 된다.