(C++) BOJ/백준 2230 - 수 고르기

문제 출처 : BOJ 2230 - 수 고르기 www.acmicpc.net/problem/2230

 

마지막으로 투 포인터를 연습해보는 문제이다.

주어진 수열에서 두 수의 차이가 m 이상인 것 중 최솟값을 구하는 문제이다.

 

최종 코드

#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 100001
#define MAX_GAP 2000000000

int arr[MAX];

bool f(int a, int b) {
	return a > b;
}

int main() {
	int n, m, l = 0, r = 0, gap = 0, min = MAX_GAP;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	
	sort(arr, arr + n, f);

	while (1) {
		if (r == n) break;
		gap = arr[l] - arr[r];
		if (gap >= m) {
			if (gap < min)
				min = gap;
			l++;
		}
		else r++;
	}
	cout << min << '\n';

	return 0;
}

일단 배열을 내림차순으로 정렬해 준 다음에,

l, r을 이용해서 두 수의 차인 gap을 구하고,

gap이 min보다 작으면 min을 gap으로 초기화 해주는 걸 반복했다.

 

다른 투 포인터 문제들은 부분합을 구하는 것이 많았는데,

이 문제는 조금 달라서 신기했다.

 

내가 골드 문제를 풀다니 왕신기하다