[BOJ]11003 최솟값 찾기

미해결(로직은 비슷하게 구성)

• sol1: deque를 활용한 풀이
• stack 상위 버전의 문제에서 복잡해진 방식(top() => front() & back())으로 풀이 가능
• deque가 비지 않았고, dq.back().second >= num이라면 => dq.pop_back()
• deque에 {i, num} 삽입
• deque의 front().first + L <= i라면 => 탐색X = dq.pop_front()

#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  int N, L;
  deque<pair<int, int>> dq;
  cin >> N >> L;
  for (int i = 0; i < N; ++i) {
    int num;
    cin >> num;
    // 새 숫자가 deque내에서 가장 큰 값의 숫자이고 마지막(back)에 위치하도록 구현
    // deque안 숫자들은 오름차순 상태를 유지하게 됨
    // 구간 내 가장 작은값은 항상 맨앞(front)에 있는 상태가 됨
    while(!dq.empty() && dq.back().second >= num){
        dq.pop_back();
    }
    // 새로운 숫자는 항상 삽입
    dq.push_back({i, num});
    // 주어진 구간을 벗어나는 outdate된 숫자 제거
    if(dq.front().first <= i - L){
        dq.pop_front();
    }
    cout << dq.front().second << ' ';
  }
  return 0;
}

• sol2: priority_queue을 활용한 풀이
• priority_queue의 Pred를 활용한 정렬 기준 설정법

#include <bits/stdc++.h>
using namespace std;
priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  int N, L;
  cin >> N >> L;
  int x, idx, cur;
  for(int i = 0; i < N; i++) {
    cin >> x;
    pq.push({x, i});
    cur = pq.top().first;
    idx = pq.top().second;
    while(idx < max(0, i - L + 1)) {
      pq.pop();
      cur = pq.top().first;
      idx = pq.top().second;
    }
    cout << cur << ' ';
  }
}