[백준/BOJ] 1306 달려라 홍준 (c++)

[백준/BOJ] 1306 달려라 홍준 (c++)

1306번: 달려라 홍준

2025.03.10 - [Competitive Programming] - 17. 슬라이딩 윈도우 (Sliding window, c++)

17. 슬라이딩 윈도우 (Sliding window, c++)

---

총 칸 수 N과 시야의 범위 M 이 주어질 때 시야 범위 내에서 가장 강력한 빛의 크기를 구하는 문제입니다.

 

M 크기의 슬라이딩 윈도우를 사용해 O(N)에 문제를 해결할 수 있습니다.

 

왼쪽에서 오른쪽으로 배열을 탐색하며 Deque에 특정 요소들을 관리합니다.

 

Deque에서 슬라이딩 윈도우의 범위를 알아야 하기 때문에 값들의 인덱스 번호를 저장합니다.

 

Deque의 Front에서는 현재 슬라이딩 윈도우 범위를 초과한 요소들을 제거합니다.

 

슬라이딩 윈도우에 새로 추가될 요소에 대해 Back에서는 Deque가 비게되거나 자신보다 큰 값이 나오게될 때 까지 모든 값을 제거합니다. 

 

새로 추가될 요소보다 작은 값들은 더 이상 슬라이딩 윈도우 구간에서 최대값이 될 수 없기 때문입니다.

 

이 과정을 거친 후 Deque에 값을 추가합니다. 이 때, Front에 있는 값이 현재 슬라이딩 윈도우에서의 최대값이 됩니다.

---

#include <bits/stdc++.h>
using namespace std;
#define REP(i, s, e) for (int i=s; i<e; i++)
int N, M;
vector<int> a;

int solve() {
    deque<int> dq;
    REP(i, 1, 2*M) {
        while(!dq.empty() && a[dq.back()] < a[i]) dq.pop_back();
        dq.push_back(i);
    }
    cout << a[dq.front()] << " ";
    REP(i, M+1, N-M+2) {
        if (dq.front() < i-(M-1)) dq.pop_front();
        while (!dq.empty() && a[dq.back()] < a[i+(M-1)]) dq.pop_back();
        dq.push_back(i+(M-1));
        cout << a[dq.front()] << " ";
    }
    return 0;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    int x;
    a.push_back(0);
    REP(i, 0, N) {
        cin >> x;
        a.push_back(x);
    }
    solve();
    return 0;
}