[C++][백준 2230] 수 고르기

문제

접근 방법

N^2로 해결하면 시간 초과가 난다.
그렇다면 최대한 줄여주는 게 좋다.
이 문제에서 요구하는 건 차이의 최소이다. 그렇다는 건 가장 가까운 수끼리 모이게 해주는 게 좋다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int abs(int num)
{
    return num < 0 ? -num : num;
}
int min(int num1, int num2)
{
    return num1 > num2 ? num2 : num1;
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int N, M, ret = 2000000000, front = 0, back = 0;
    cin >> N >> M;
    vector<int> A(N);
    for (int i = 0; i < N; ++i)
        cin >> A[i];
    sort(A.begin(), A.end());
    while (true)
    {
        int gap = abs(A[back] - A[front]);
        if (gap >= M)
        {
            ++front;
            ret = min(ret, gap);
            if (gap == 0)
                break;
            else if (front == back)
                ++back;
        }
        else
        {
            ++back;
        }
        if (back == N)
            break;
    }
    cout << ret;
    return 0;
}

풀이

정렬한 수에서 M 이상인 차이를 찾아주면 된다.
작은 수와 큰 수로 나누어 2개의 포인터로 확인하면 된다.
M 이상인 경우 작은 수의 포인터를 옮겨서 차이를 낮추고 M보다 작다면 큰 수의 포인터를 옮겨서 M 이상으로 만들어 준다.
만약 큰 수의 포인터가 끝에 도달했다면 더 이상 M 이상의 수가 존재하지 않으므로 종료해 준다.