[백준 2230] 수 고르기

문제

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이 된다.

입력

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

출력

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

 

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL)
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, INF = 9876543210;
int n, s, m, x, l, r, ans = INF;
int a[100001];
int main() {
	FAST;
	cin >> n >> m;
	rep(i, n) {
		cin >> a[i];
	}
	sort(a, a + n);
	int ri = 0;
	rep(le, n) {
		while (ri < n && a[ri] - a[le] < m)ri++;
		if (ri == n)break;
		ans = min(ans, a[ri] - a[le]);
	}
	cout << ans;
}

 

한 배열위에 두 값의 차이가 M보다 크고, 가장 작은 수를 구하는 문제입니다.

해당 배열을 정렬하면, 투 포인터를 사용할 수 있습니다.

 

이전 문제와 마찬가지로, 왼쪽 포인터가 고정되어있을때 오른쪽 포인터가 한번 조건을 만족시키면 그 이후로는 움직일 이유가 없습니다. 두 포인터의 데이터의 차이가 계속해서 커지기 때문입니다.

 

따라서 만약 오른쪽 포인터를 계속 움직이다가 조건을 만족한다면, 왼쪽포인터를 한칸 오른쪽으로 옮기고 다시 진행할 수 있습니다.