최솟값 찾기
문제
N개의 수 A1, A2, …, AN과 L이 주어진다.
Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오.
이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.
입력
첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000)
둘째 줄에는 N개의 수 Ai가 주어진다. (-109 ≤ Ai ≤ 109)
출력
첫째 줄에 Di를 공백으로 구분하여 순서대로 출력한다.
1
2
3
4
5
6
예제 입력 1
12 3
1 5 2 3 6 2 3 7 3 5 2 6
예제 출력 1
1 1 1 2 2 2 2 2 3 3 2 2
풀이
범위를 이동해가며 최솟값을 찾는 문제이다.
가장 먼저 생각난 것은 슬라이싱 윈도우인데 적용 아이디어가 떠오르지 않는다.
메모를 까보니 우선순위 큐나 덱이라는데 질문 글들을 보니 덱을 이용하는게 정해 같다.
아이디어가 특이하다고 해야될까. 생각하긴 어려웠다.
우선 덱을 만들고 배열의 시작부터 하나씩 집어 넣는다.
만약 덱이 비어있다면 그냥 넣으면 되고, 값이 있으면 맨 뒤보다 큰지 작은지 확인한다.
맨 뒤보다 넣을 값이 크다면 그냥 넣고, 작다면 넣읗값이 커질때까지 맨 뒤를 pop해준다.
그 이유를 보면 1 5 2 3 6 2 3 7 3 5 2 6가 입력되는 과정을 보자.
맨 처음 1이 들어가고, 5가 들어간다. 1, 5가 덱에 있는데 2가 들어올 차례다.
범위를 슬라이싱한다고 하면 2가 5뒤에 있는데 그렇다면 어떠한 범위에서도 5는 최솟값이 될 수 없다.
그렇기에 5는 pop해주고 2를 집어 넣는 것이다.
이를 적용하면 더 작은 숫자가 들어왔을 때 앞에 숫자가 크다면 앞의 숫자는 어떤 범위에서도 최솟값이 될 수가 없다.
그렇기에 숫자를 넣을 때 더 큰 숫자는 pop해주면 되는 것이다.
그러고서 범위가 하나씩 잘리는데, 앞에서 짤리는 수들이 덱의 맨 앞과 같다면 pop_front한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <vector>
#include <string>
#include <functional>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <math.h>
using namespace std;
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c;
int n, m, t;
cin >> n >> m;
vector<int> v(n);
for(int i=0;i<n;i++){
cin >> v[i];
}
deque<int> d;
d.push_back(v[0]);
cout << v[0] << ' ';
//뒤에 있는데 작은 것이 들어오면 다 사라져야함.
for(int i=1;i<n;i++){
while(d.size()>0 && d.back()>v[i]){
d.pop_back();
}
d.push_back(v[i]);
if(i-m>=0){
if(v[i-m]==d.front()){
d.pop_front();
}
}
cout << d.front() << ' ';
}
return 0;
}