[문제 링크](https://www.acmicpc.net/problem/2230)
💡 정렬/두 포인터
Memory: 2800KB Time: 68ms Code Length: 506B
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
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N, M;
vector<int> dict;
void init() {
cin >> N >> M;
for (int i = 0; i < N; i++) {
int num;
cin >> num;
dict.push_back(num);
}
sort(dict.begin(), dict.end());
}
int solve() {
int en = 0;
int mn = 2'000'000'001;
for (int st = 0; st < N; st++) {
while (en < N && dict[en] - dict[st] < M) en++;
if (en == N) break;
mn = min(mn, dict[en] - dict[st]);
}
return mn;
}
int main() {
init();
cout << solve();
}
init() 함수는 N과 M을 입력받고, N개의 숫자를 입력받아 dict 벡터에 저장한 뒤 오름차순으로 정렬한다.
solve() 함수는 시작점(st)을 기준으로 끝점(en)을 이동시키면서 dict[en] - dict[st]가 M보다 작은 경우에 en을 증가시킨다. 이 과정을 반복하면서 최소 간격을 구하고, 그 값을 반환한다.
main() 함수에서는 init() 함수를 호출하여 초기화를 수행하고, solve() 함수를 호출하여 문제를 해결한 뒤 결과를 출력한다.
