[BOJ/C++] 2230번 수 고르기

https://www.acmicpc.net/problem/2230

1. 수열 길이 N과 차이 최솟값 M 입력받기

2. 수열 내에서 두 수의 차이가 M보다 크면서 가장 작은 차이 출력

 

첫번째 방법은 2개로 집합 만들 수 있는 경우의 수 모두 구하기 -> 시간초과 걸리기 딱좋음

두번째 방법은 투포인터! 수열 정렬 후 포인터 두개를 시작지점에 두고 시작

두 수의 차이가 m보다 작으면 오른쪽 포인터를 한칸 움직이기

m보다 크면 min값과 비교, 왼쪽 포인터를 한칸 움직이기

 

#include <iostream>
#include <algorithm>
using namespace std;
long long m, n;
long long a[100000];
long long mini = 2000000000;
int main()
{

    cin >> n >> m;
    int left = 0, right = 0;

    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }

    sort(a, a + n);

    while (right < n)
    {
        long long diff = a[right] - a[left];
        if (diff < m)
        {
            right++;
        }
        else
        {
            mini = min(mini, diff);
            left++;
        }
    }

    cout << mini;
}