기본적으로 슬라이딩 윈도우를 써야겠다!고는 생각했으나, 잘 안되서 결국 인터넷 검색을 참고했다.
기본 C로는 배열을 이용해서 덱을 구현해야 할 것 같으나, C++을 써서 deque 라이브러리를 이용했다.
deque(덱)은 queue와 달리 앞으로도 넣을 수 있는 구조이다.
덱에 숫자를 넣어가면서 각 단계별 최솟값을 구하면 된다.
예제를 보면서 원리를 이해하는 것이 낫다.
예제 1번을 보면,
1은 혼자니까 그냥 덱에 넣는다. 이 상태에서 덱의 가장 앞에 있는 값(최솟값)은 1이므로 1을 출력한다.
5를 넣고자 한다, 만약 덱에 맨 뒤에 있는 값이 5보다 크면 빼버린다. 이를 5보다 작은 수가 덱의 맨 뒤에 있을 때까지 반복한다. (여기선 없으니까 뺄 게 없다)
덱의 최솟값은 1이다. 1을 출력한다.
2를 넣고자 한다, 아직 맨 뒤에 있는 값인 5가 2보다 크므로 빼버린다. 어차피 뒤로 가도 5가 먼저 빠지지 2가 먼저 빠지지 않으므로 5와 2가 함께 있을 땐 항상 2가 최솟값이다. 그래서 5는 존재가 무의미하다.
여전히 최솟값은 1이다. 1을 출력한다.
3을 넣으려고 한다. 이제 맨 처음에 넣었던 input[cur-3]이 덱에 없어야 한다. 근데 1이 아직 남아있다. 덱의 맨 앞에 있는 1을 지운다. 덱 의 끝 값(2)가 3보다 크지 않으므로 뺄 것이 없다. 3을 넣어준다. 최솟값은 2이다.
6을 넣으려고 한다. input[cur-3]인 5는 덱에 없다. 따라서 지울 것이 없다. 덱의 끝이 6보다 작으므로 덱의 뒤에서 빼낼 것도 없다. 최솟값은 2이다.
2를 넣으려고 한다. input[cur-3]인 2가 아직 덱의 맨 앞에 있다. 덱에서 맨 앞의 2를 지운다. 2를 덱의 뒤에 넣으려고 보니, 2보다 큰 6이 있다. 6을 덱에서 빼버린다. 아직 덱의 뒤에 2보다 큰 3이 있다. 3도 덱에서 빼버린다. 이제 덱이 비어버렸으니 2를 그냥 넣는다. 최솟값은 새로 들어간 2이다.
3을 넣으려고 한다. input[cur-3]인 3은 없다. 덱의 맨 뒤도 3보다 작다. 덱에 3을 넣는다.
최솟값은 2이다.
이런 식으로 쭉 해가면, 덱의 맨 앞에 있는 것은 항상 cur-2 ~ cur 간의 최솟값이 될 수 있다.
작성 코드
#include <iostream>
#include <cstring>
#include <deque>
using namespace std;
#define MAXN 5000000
int N, L;
int input[MAXN + 1];
deque<pair<int, int> > dq; // 값, 인덱스
int main(void) {
freopen("in.txt", "r", stdin);
ios::sync_with_stdio(false);
cout.tie(NULL);
cin.tie(NULL);
cin >> N >> L;
for (int i = 0; i < N; i++) {
cin >> input[i];
}
for (int i = 0; i < N; i++) {
if (dq.empty()) {
dq.push_back(make_pair(input[i], i));
}
else {
if (dq.front().second < i - L + 1) dq.pop_front();
while (!dq.empty() && dq.back().first > input[i]) {
dq.pop_back();
}
dq.push_back(make_pair(input[i], i));
}
cout << dq.front().first << " ";
}
return 0;
}
