[BaekJoon] 2230번 수고르기

• 이 글은 C++로 풀이를 작성하였습니다.

문제

예시

 

풀이

• 다음 문제는 이분탐색으로도 해결할 수 있습니다. 해당 수열을 정렬 후 처음 인덱스부터 끝까지 탐색을 하되 해당 인덱스의 값보다 M이 큰 값을 이분탐색을 하여 삽입할 인덱스를 찾을 수 있습니다. 즉, 정렬을 무너뜨리지 않고 해당 값을 추가할 인덱스(lower_bound)를 반환합니다.
• 하지만, 투 포인터 라는 알고리즘을 사용해서 풀이를 하려고 합니다. 이 문제에서 투 포인터를 사용하면 정렬할 때 O(NlogN)과 수를 고르는 방법 O(N)으로 시간복잡도는 O(NlogN)이 됩니다.

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

int main(){
    int arr[100000];
    int n,m;
    cin>>n>>m;

    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    sort(arr, arr+n);

    int result = 2000000000;
    int s = 0;
    int e = 0;
    while(s!=n && e!=n){
        if(arr[e] - arr[s]>=m){
            result = min(result, arr[e]-arr[s]);
            s++;
        }else{
            e++;
        }
    }

    cout<<result;
}

• 추가로 궁금한 점이나 수정할 부분 있으면 댓글로 남겨주세요.