문제 : https://www.acmicpc.net/problem/2433
2433번: The Sound of Silence
첫째 줄에 샘플의 수 n (1 ≤ n ≤ 1,000,000), m (1 ≤ m ≤ 10,000), c (0 ≤ c ≤ 10,000)가 주어진다. 둘째 줄에는 각 샘플의 값 ai가 주어진다. (0 ≤ ai ≤ 1,000,000 for 1 ≤ i ≤ n)
www.acmicpc.net
문제 파악하기
최솟값과 최댓값의 차이가 C이하인 M개의 연속된 숫자가 있는지 탐색하는 문제입니다. 최대 1,000,000개의 숫자에 대해 10,000개의 연속된 숫자가 만족하는지 확인해야하는 문제이기에 완전탐색으로는 해결할 수 없습니다. 그렇기에 특정 범위에서 최댓값과 최솟값을 찾아주는 알고리즘을 사용해야 합니다.
문제 해결하기
가장 기본적인 해결방법은 세그먼트 트리를 사용하는 방법입니다. 1,000,000개의 데이터에 대해 10,000개의 범위를 탐색할 때, 세그먼트 트리를 사용하면 O(NlogM) 시간 복잡도를 가지며, 이정도 데이터의 개수라면 1초 안에 해결할 수 있습니다. 최솟값과 최댓값을 미리 구해놓은 세그먼트 트리를 사용해서 N개의 숫자를 모두 확인하면 문제를 해결할 수 있습니다.
이 문제를 해결하는 다른 방법으로는 덱을 사용해서 해결할 수 있습니다. 우선 [i-M+1, i] 범위의 값을 저장할 2개의 덱을 만듭니다. 첫 번째 덱은 범위 내 가장 작은 값(최솟값)을 구하는 덱입니다. 두 번째 덱은 반대로 범위 내 가장 큰 값(최댓값)을 구하는 덱입니다. 왜 최솟값과 최댓값을 구하는데 덱을 사용할까요? 이는 범위가 계속 바뀌기 때문입니다. 우리는 N개의 데이터에 대해 [i-M+1, i] 범위 내 최솟값과 최댓값을 구하고 싶습니다. 만약 현재 값(inp[i])이 어떤 범위에서도 최솟값이나 최댓값이 아니라면 상관없습니다. 하지만 현재 값이 만약 어떤 범위의 최솟값 혹은 최댓값이라면 꼭 나중에 참고해야 합니다. 다만, 모든 값을 저장하고 참고하는건 너무 비효율적입니다. 그렇기에 우리는 현재 값(inp[i])을 각각의 덱에 저장하되, 최솟값을 저장하는 덱에는 항상 현재 숫자보다 작은 값만을 저장하고 최댓값을 저장하는 덱에는 항상 현재 숫자보다 큰 값만 저장해놓으면 됩니다. 이는 만약 최솟값을 구한다고 가정했을 때, 현재 값보다 큰 값들은 절대 최솟값이 될 수 없기 때문입니다. 최댓값을 구할 때에도 현재 값보다 작은 값이 있다면 해당 값은 절대 최댓값이 될 수 없습니다. 그렇기에 덱을 현재 값을 기준으로 값을 유지해놓으면 쉽게 문제를 풀 수 있습니다.
소스코드
세그먼트 트리를 사용한 소스코드
|
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
#include <stdio.h>
#include <vector>
#include <algorithm>
#define NMAX 1000010
#define MAX 0x7FFFFFFF
using namespace std;
int N, M, C, t;
vector< int > inp;
int sz, vmin, vmax;
int segTree[NMAX*4][2];
vector< int > ans;
int segSearch(int l, int r, int idx) {
int ret;
if(idx == 0) ret = 0;
else ret = MAX;
while(l<=r) {
if(l%2 == 1) {
if(idx == 0) ret = max( ret, segTree[l++][idx] );
else ret = min( ret, segTree[l++][idx] );
}
if(r%2 == 0) {
if(idx == 0) ret = max( ret, segTree[r--][idx] );
else ret = min( ret, segTree[r--][idx] );
}
l/=2; r/=2;
}
return ret;
}
int main() {
// 입력
scanf("%d %d %d", &N, &M, &C);
for(int i=0;i<N;i++) {
scanf("%d", &t);
inp.push_back(t);
}
// 세그먼트 트리( [0]: 최댓값 / [1]: 최솟값 )
for(sz=1;sz<N;sz*=2);
for(int idx=sz*2;idx>=1;idx--) {
if(sz+N <= idx) segTree[idx][1] = MAX;
else if(sz <= idx) segTree[idx][0] = segTree[idx][1] = inp[idx-sz];
else {
segTree[idx][0] = max( segTree[idx*2][0], segTree[idx*2+1][0] );
segTree[idx][1] = min( segTree[idx*2][1], segTree[idx*2+1][1] );
}
}
// 탐색
for(int i=0;i+M<=N;i++) {
vmax = segSearch(i+sz, (i+M-1)+sz, 0);
vmin = segSearch(i+sz, (i+M-1)+sz, 1);
if(vmax - vmin <= C) ans.push_back(i+1);
}
// 출력
if(ans.empty()) printf("NONE");
else {
for(int val:ans) printf("%d\n", val);
}
}
|
cs |
덱을 사용한 소스코드
|
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
|
#include <stdio.h>
#include <deque>
#include <vector>
#include <utility>
#define PAIR pair<int, int>
using namespace std;
int N, M, C, t;
deque< PAIR > vmin, vmax;
vector< int > ans;
int main() {
scanf("%d %d %d", &N, &M, &C);
for(int i=1;i<=N;i++) {
scanf("%d", &t);
if(i == 1) {
vmin.push_back({t, i});
vmax.push_back({t, i});
}
else {
// 범위 이외의 값이 있는지 확인
if(vmin.front().second == i-M) vmin.pop_front();
if(vmax.front().second == i-M) vmax.pop_front();
// 오름차순으로 넣기
while(!vmin.empty() and vmin.back().first >= t) vmin.pop_back();
vmin.push_back({t, i});
// 내림차순으로 넣기
while(!vmax.empty() and vmax.back().first <= t) vmax.pop_back();
vmax.push_back({t, i});
}
if(i-M+1>0 and vmax.front().first - vmin.front().first <= C) ans.push_back(i-M+1);
}
if(ans.empty()) printf("NONE");
else {
for(int val:ans) printf("%d\n", val);
}
}
|
cs |
후기
처음에는 세그먼트 트리로 풀었다가 덱으로 다시 풀어본 문제입니다. 덱을 사용하는 노하우가 없어서 그런지 조금은 헷갈렸지만 재미있는 알고리즘이라고 생각합니다. 덱에 관련된 문제를 좀 더 풀어보고 싶은 마음이 드는 문제입니다.