[백준]수 고르기(2230) - C++

✏️ 문제

N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오.

예를 들어 수열이 {1, 2, 3, 4, 5}라고 하자. 만약 M = 3일 경우, 1 4, 1 5, 2 5를 골랐을 때 그 차이가 M 이상이 된다. 이 중에서 차이가 가장 작은 경우는 1 4나 2 5를 골랐을 때의 3이 된다.

⛔️ 제약조건

• 1 ≤ N ≤ 100,000
• 0 ≤ M ≤ 2,000,000,000
• 0 ≤ |A[i]| ≤ 1,000,000,000

🎈 입력형식

첫째 줄에 두 정수 N, M이 주어진다. 다음 N개의 줄에는 차례로 A[1], A[2], …, A[N]이 주어진다.

🎈 출력형식

첫째 줄에 M 이상이면서 가장 작은 차이를 출력한다. 항상 차이가 M이상인 두 수를 고를 수 있다.

🎈 입출력 예

<입력>
3 3
1
5
3
<출력>
4

👩‍💻 내 코드 - Two Pointer

#include <iostream>
#include <algorithm>
using namespace std;

int n, m;
int arr[100001];
int sub_val;
int min_val = 2134567890;

void input() {
	cin >> n >> m;

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

	sort(arr, arr + n);

}

void find() {
	int left = 0;
	int right = 0;

	while (right <= n) {

		sub_val = arr[right] - arr[left];
		
		if (sub_val >= m) {
			min_val = min(sub_val, min_val);
			left++;
		}
		else {
			right++;
		}
	}
}

void output() {
	cout << min_val;
}

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

	input();
	find();
	output();

}

💡 새롭게 배운 것

배열 정렬

• 오름차순

sort(arr, arr+n);

• 내림차순

bool desc(int a, int b) {
 return a > b;
}
sort(arr, arr+n, desc);

vector 정렬

• 오름차순

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

• 내림차순

sort(v.rbegin(), v.rend());
sort(v.begin(), v.end(), desc);