무식하게 모든 위치의 칸을 계산하면 최대 입력인 , 에서는 회의 연산을 하게 된다.
발상 1 - Priority Queue 활용
입력될 때 마다 PQ 에 추가한다. 일정 범위 내의 ‘최솟값’을 출력하면 되므로 PQ를 활용해 우선 최솟값부터 뽑아낸다. 만약 뽑은 최솟값이 나왔던 인덱스가 현재 인덱스로부터 이상 떨어져있다면 그 최솟값은 현재 인덱스에서 사용할 수 없는 값이므로 PQ에서 제거한다. 현재 인덱스로부터 범위 안에 있는 인덱스를 가진 수가 나올 때 까지 PQ를 pop한다. 이 때 pop되는 수들은 오름차순 정렬되어있으므로 가장 처음 조건을 만족하는 수가 항상 현재 위치에서의 최솟값임이 보장된다. PQ의 push/pop 동작은 모두 이고 push와 pop이 각각 최대 번씩 발생하므로 시간 복잡도는 이 된다.
코드 1
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
struct v {
int idx, v;
};
struct cmp{
bool operator() (v a, v b) {
return a.v > b.v;
}
};
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, k; cin >> n >> k;
vector<int> arr(n + 1); priority_queue<v, vector<v>, cmp> pq;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
}
for (int i = 1; i <= n; i++) {
int s = i >= k ? i - k + 1 : 1;
pq.push({ i, arr[i] });
while (pq.empty() == false && pq.top().idx < s) pq.pop();
cout << pq.top().v << " ";
}
return 0;
}발상 2 - Deque 활용
모든 구간에 대해 별도로 최솟값을 구하는게 아니라 이전 구간의 정보를 Deque에 저장하고 그 정보를 활용해 상수 시간에 구간의 최적값을 업데이트하는 자료구조를 만들 수 있다. 구간이 옮겨질 때마다 실제로 덱에 발생하는 변경점은 인덱스가 벗어난 원소 1개 제거, 새로 추가되는 원소 1개 추가가 전부다. 구간의 값들 중 딱 1개만 새로운 수로 갱신되는 것이다. 주어진 수열을 인덱스 순으로 순회할 때 앞서 나왔던 수 가 현재 수 보다 크다면 그 수는 이상의 인덱스에서는 절대 최솟값이 될 수 없다. ( 라는 점을 꼭 기억해야 한다. ) 그 이유는 아래와 같다.
가 어떤 구간 의 최솟값이 되기 위해선 와 같은 구간에 속하면 안된다. 그런데 우리는 탐색할 때 구간을 순차적으로 옮기고 있으므로 구간에서 먼저 벗어나는 수는 가 될 수 밖에 없다. 즉, 와 가 같은 구간에 속하게 되는 시점부터 는 최솟값이 되는 것이 불가능하다. 즉, 는 가 덱에 삽입되는 순간부터 최솟값 후보에서 제외할 수 있다.
따라서 최솟값 후보들을 덱에 모아놓고 새로운 수 와 비교하며 후보군에서 최솟값이 될 수 없는 후보들을 선별해 제거할 수 있다. 먼저 덱 맨 앞은 가장 들어온지 오래된 수들이므로 앞에서부터 인덱스가 을 초과하는 수들을 제거한다. 그 후 덱 맨 뒤에서부터 값이 현재 수보다 큰 수들을 제거하면 최소값이 될 가능성이 없는 수를 미리 제거할 수 있다. 뒤에서부터 제거하는 이유는 위 방법대로 탐색했을 때 덱에 들어가는 수들은 오름차순으로 정렬되기 때문이다. 덱의 push / pop 은 front / back에 상관없이 모두 의 복잡도를 가지고 주어진 수 하나당 최대 2번의 연산 (push 1번 pop 1번)을 수행하게 되므로 알고리즘의 시간 복잡도는 이다. (단, 덱은 내부 구현이 복잡해 상수 복잡도긴 하지만 상수가 조금 크다고 한다. 이 큰 상수를 가리켜 덱 상수라고도 한다. )
코드 2
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;
struct node {
int i, v;
};
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, k; cin >> n >> k; vector<int> arr(n + 1); deque<node> dq;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
}
dq.push_back({ 1, arr[1] });
cout << arr[1] << " ";
for (int i = 2; i <= n; i++) {
while (!dq.empty() && i - dq.front().i >= k) dq.pop_front();
//while (!dq.empty() && dq.back().v >= arr[i]) dq.pop_back();
while (!dq.empty() && dq.front().v >= arr[i]) dq.pop_front();
dq.push_front({ i, arr[i] });
cout << dq.front().v << " ";
}
return 0;
}