[백준/C++]2230번: 수 고르기

수 고르기

아이디어

투포인터 알고리즘을 사용했다.
투포인터 알고리즘은
1. start = end = 0
2. 항상 start <= end를 만족한다.

start=0, end=0부터 시작해서

• sub가 m보다 작을 경우 end++를 해주었다.
• sub가 m보다 같거나 클 경우 start++를 해주고 sub가 ans보다 작은 경우 ans를 갱신시켜준다.
  그 이유는 end번째 숫자에서 start번째 숫자를 뺐을때 sub보다 더 작은 경우는 없기 때문이다. (end번째 이후의 숫자들은 오름차순으로 정렬이 되어있다)

  1 2 3 5에서
  3 - 1 = 2
  5 - 1 = 4 이므로
  굳이 start를 가만히 놔둘 필요가 없다.

• end < n을 추가한 이유는

  1 2 3 4 5
  m = 1000

라는 케이스인 경우, end가 계속 증가하기 때문에 배열 범위를 넘어갈 수 있다. 이를 방지하기 위함

제출 코드

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

using namespace std;

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

	int n, m, ans = 2000000000;
	cin >> n >> m;

	vector<int> v(n);

	for (int i = 0; i < n; i++)
		cin >> v[i];

	sort(v.begin(), v.end());

	int start = 0, end = 0;

	while (start <= end && end < n)
	{
		int sub = v[end] - v[start];

		if (sub < m) // 답이 아님
			end++;
		else
		{
			ans = min(ans, sub);
			start++;
		}
	}

	cout << ans;

	return 0;
}