[백준 2230번] 수 고르기 (C++)

문제링크 : https://www.acmicpc.net/problem/2230

2230번: 수 고르기

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 2000000001;

int N, M, arr[100001];

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

    cin >> N >> M;
    for(int i=0; i<N; i++) cin >> arr[i];
    sort(arr, arr+N);

    int minV = MAX;
    for(int i=0; i<N-1; i++)
    {
        int idx = lower_bound(arr+i, arr+N, arr[i]+M) - arr; //i기준 M이상 큰 수 위치
        if(idx>=N) continue; //범위 체크
        minV = min(minV, arr[idx]-arr[i]); //차이가 가장 작은 값 저장
    }

    cout << minV;

    return 0;
}

 

현재 i 기준 M이상 큰 수의 위치를 lower_bound를 통해 찾는다.

이렇게 찾은 위치의 값 - 현재 i 위치의 값을 하면 우리가 찾는 M이상의 차이가 나는 값을 얻게 된다.

모든 i에 대해 이를 탐색하여 차이값이 가장 작은 값을 구해준다.

 

이때 주의해야 할 점은 idx를 구할 때 현재 i 기준 만족하는 값이 없다면 무조건 마지막 수의 다음 위치를 반환한다.

따라서 기존 범위를 초과해버리는 경우가 생기기에 idx위치가 N이상인지 체크를 해주어야한다.