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

https://www.acmicpc.net/problem/2230

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이상인 두 수를 고를 수 있다.

 

이분탐색을 응용한 lower_bound를 이용해서 해결할 수 있고, 또 투포인터를 이용해서 해결할 수 있다.

 

lower_bound로 해결하려고 하면 하나의 for문으로 처음부터 끝까지 값을 지정하고 그 값에 M을 더한다. 

그리고 그 합한 값의 lower_bound를 찾고 그 위치가 배열 내에 있다면 그 위치의 값과 처음에 지정한 값의 차가 M 이상이 될 수 있다는 것이다. 이것을 이용하여 해결한다면 O(nlogn)으로 해결이 가능하다.

 

투포인터로 해결하고자 한다면 처음 인덱스에 시작점과 끝점을 모두 둔다.

그리고 각 인덱스 차이값이 M보다 작으면 두 값의 차이가 M보다 크거나 같아질 때까지 단, 끝 인덱스가 배열 크기보다 작은 경우에만 끝점을 하나씩 옮겨준다.

그리고 M보다 크거나 같아지면 두 개의 차이값을 계속해서 갱신해주는 방법이다.

이 방법은 O(n)으로 해결이 가능하다

 

lower_bound로 해결한 방법

#include<iostream>
#include<cmath>
#include<list>
#include<stack>
#include<tuple>
#include<map>
#include<algorithm>
#include<vector>
#include<deque>
#include<queue>
#define CUNLINK ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define MAX_SIZE 1003
#define INF 987654321
using namespace std;
typedef long long ll;

int N;
ll M;
vector<int> arr;

int main() {
	CUNLINK;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		arr.push_back(x);
	}
	sort(arr.begin(), arr.end());
	
	ll Answer = 20000000001;
	for (int i = 0; i < N; i++) {
		ll x = arr[i];
		ll a = lower_bound(arr.begin(), arr.end(), x + M) - arr.begin();
		//cout << a << endl;
		if (a < arr.size()) {
			Answer = min(Answer, arr[a] - x);
		}
	}
	cout << Answer << endl;
	
	return 0;
}

투포인터로 해결한 방법

#include<iostream>
#include<cmath>
#include<list>
#include<stack>
#include<tuple>
#include<map>
#include<algorithm>
#include<vector>
#include<deque>
#include<queue>
#define CUNLINK ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define MAX_SIZE 1003
#define INF 0x7fffffff;
using namespace std;
typedef long long ll;

int N;
ll M;
vector<int> arr;

int main() {
	CUNLINK;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		arr.push_back(x);
	}
	sort(arr.begin(), arr.end());
	int en = 0;
	int answer = INF;
	for (int st = 0; st < N; st++) {
		while (en < N && arr[en] - arr[st] < M) en++;
		if (en == N) break;
		answer = min(answer, arr[en] - arr[st]);
	}
	cout << answer;
	
	return 0;
}