백준 2230 수 고르기

문제링크

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

문제

풀이

이분탐색을 이용하여 풀었다.
(다른 풀이를 보니 투 포인터로 좀 더 간단히 풀린다.)

1. 먼저 정렬 후 배열의 첫 원소를 기준으로 잡는다.
2. 기준 원소보다 큰 원소들에 대해 이분 탐색으로 기준원소와의 차이가 m 이상이면서 그 크기가 가장 작은 원소를 찾아준다.
3. 기준 원소와의 차이가 기존의 diff 값보다 작으면 diff 값을 갱신한다.
4. 반복문을 통해 기준 원소를 옮겨가며 같은 작업을 반복한다.

시행착오

투포인터를 이용한 풀이는 정렬 O(nlogn), 투포인터 탐색O(n) 의 풀이이다.
하지만 위 풀이는 정렬O(nlogn), 이분탐색O(nlogn) 으로 조금 더 비효율적인 풀이이다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
#define INF 2147483647
vector<int> v;
int n, m;
int diff = INF;

void solve(int idx) {
	int l = idx, r = v.size() - 1;

	while (l + 1 < r) {
		int mid = (l + r) / 2;
		if (v[mid] - v[idx] >= m) r = mid;
		else l = mid;
	}
	
	if (v[r] - v[idx] < diff && v[r]-v[idx]>=m) {
		diff = v[r] - v[idx];
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		int t;
		cin >> t;
		v.push_back(t);
	}
	sort(v.begin(), v.end());
	
	for (int i = 0; i < v.size(); i++) solve(i);
	cout << diff;
	
}

후기

열심히 하자