BOJ 2230 - 수 고르기

2230번: 수 고르기 (acmicpc.net)

2230번: 수 고르기

 

접근 방법

이분 탐색으로 이 문제를 해결하려고 했다.

두 수를 고르는 것이기 때문에 하나(i)를 for을 돌면서

각 수 위에서부터 끝까지(i+1~n) 수를 이분탐색을 하면서 돌면된다고 생각.

 

이분탐색의 경우, 하나를 모두 돌면서 진행되므로 O(N*logN)이 수행되지만,

이를 투포인터를 이용할 경우, 모든 수를 한 번씩만 돌기 때문에 O(N)에 수행이 가능하다.

 

따라서, 투포인터가 더 빠른 실행 시간을 자랑한다.

 

참고

글 읽기 - 이분탐색을 이용해서 해보려고 했습니다. 뭐가 문제일까요? (acmicpc.net)

글 읽기 - 이분탐색을 이용해서 해보려고 했습니다. 뭐가 문제일까요?

 

코드

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

#define ll long long

ll t, n, m;
ll res = 10000000000;
vector<ll> arr;



int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		ll tmp;
		cin >> tmp;
		arr.push_back(tmp);
	}

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

	ll l = 0;
	ll r = arr.size() - 1;

	ll e = 0;
	ll tmp = 0;
	for (int s = 0; s < n; s++) {
		
		while (e+1 < n && arr[e] - arr[s] < m) {
			e++;
			//cout << s <<" " <<  e << endl;
		}

		if (arr[e] - arr[s] == m) {
			res = m;
			break;
		}
		else if (arr[e]-arr[s] > m) {
			res = min(res, arr[e] - arr[s]);
		}
	}
	cout << res;
}