문제

풀이 요약

투 포인터를 활용한 문제.

풀이 상세

1. 투 포인터 $st$, $ed$ 을 지정하여 시작한다. 첫 시작은 모두 $idx = 0$ 에서 부터 시작한다.

2. 정확한 탐색을 위해 먼저 오름차순으로 정렬한 후 탐색을 시작한다

   • $diff$ 의 값이 현재 $M$ 값 보다 작다면, 더 큰 값을 보기 위해, $ed$ 를 늘린다.

   • $diff$ 의 값이 현재 $M$ 값 보다 크다면, 이후 $ed$ 의 오른쪽 부분은 모두 큰 값이 나올테니, $st$ 를 늘려, $ed$ 부분을 다시 탐색한다.

3. 탐색과정을 통해 찾아낸 최소 차이 값을 출력한다.

배운 점

• 여러 태케를 구상하여, mid 값 설정을 통한 이분탐색을 시도하려 했으나 원하는대로 구현이 되지 않았다.

• 설마 그냥 1씩 증가시키는게 될까… 했는데 되었다. 고민하다가 생각이 안나면 그냥 일단 시도해보자.

• ios::sync_with_stdio(0) , cin.tie(0) 은 쓰고 시작하자. 속도가 많이 차이난다.

• #include <bits/stdc++.h> 이제 안써야겠다! 편해서 좋은데 코테 안되는 곳도 있다 하고, c++ 이랑 좀 처럼 안 친해진다.

정답

#include <algorithm>
#include <iostream>
#define MAX 2000000001
using namespace std;
int N, M, st, ed;
int arr[100000];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    for (int i = 0; i < N; i++)
        cin >> arr[i];
    sort(arr, arr + N);
    int res = MAX;
    while (st < N && ed < N && st <= ed) {
        int diff = arr[ed] - arr[st];
        if (diff < M)
            ed++;
        else {
            res = min(res, diff);
            st++;
        }
    }
    cout << res;
}