백준 - 2230번 : 수 고르기 (C++)

풀이 방법 : 투 포인터

입력으로 주어지는 수열을 오름차순으로 정렬한 뒤 0번 인덱스부터 시작해서 차이값을 토대로 왼쪽, 오른쪽 포인터들의 인덱스를 증가시켜나간다. 같은 수를 고르는 것이 허용되는 문제이므로 Left, Right 둘 다 0에서부터 시작한다.

오름차순으로 정렬되었으므로 두 포인터 간의 인덱스가 멀어질수록 차가 더 커질 것이고 가까울 수록 차가 더 작아질 것이다.

만약 RightNum - LeftNum이 M보다 작다면 차이가 더 큰 수를 골라야 하므로 오른쪽 포인터의 값을 증가시킨다. 그 반대라면 두 수의 차의 최솟값을 갱신시켜주고 왼쪽 포인터의 값을 증가시킨다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios::sync_with_stdio(false);

	int N, M;
	cin >> N >> M;

	vector<int> vecNums(N);
	for (int i = 0; i < N; ++i)
	{
		cin >> vecNums[i];
	}

	sort(vecNums.begin(), vecNums.end());
	int Left = 0;
	int Right = 0;

	int Min = 2000000001;

	while (Left <= Right && Left < N && Right < N)
	{
		int LeftNum = vecNums[Left];
		int RightNum = vecNums[Right];

		int Minus = RightNum - LeftNum;

		if (Minus < M)
		{
			++Right;
		}

		else
		{
			Min = min(Min, Minus);
			++Left;
		}
	}

	cout << Min;
}