백준 g5 2230 수 고르기 c++

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

2230번: 수 고르기

 

문제

 

N <= 10^5인 배열이 주어진다.

배열 중 두 수를 골랐을 때 (중복 가능) 그 차가 M 이상이면서 최소의 값 구하기

 

풀이1. 이분 탐색 O(NlogN)

 

lower_bound를 이용해서 해결 가능하다. 배열의 값을 x라고 할 때 x + M 이상인 값을 찾으면 된다.

배열 정렬

for i : arr배열
	res = lower_bound(arr배열, i+M)
    
    ans 업데이트

 

코드

/*boj g5 2230 수 고르기 binary search*/
#include <algorithm>
#include <iostream>
#define MAXN 100005
using namespace std;

int N, M;
int arr[MAXN];
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    for (int i = 0; i < N; i++)
        cin >> arr[i];

    int ans = 2000000000;
    sort(arr, arr + N);

    for (int i = 0; i < N; i++) {
        int idx = lower_bound(arr, arr + N, arr[i] + M) - arr;

        if (idx == N) continue; // 값이 없을 경우

        ans = min(ans, arr[idx] - arr[i]);
    }

    cout << ans << "\n";
}

 

 

풀이2. 투포인터 (https://blog.encrypted.gg/1004

 

이중 for문으로 짰을 때, 두 가지 특징이 있다.

1. i가 증가하면 차가 M이상인 최솟값인 j도 같이 증가한다.

2. 최솟값을 구하는 문제이기 때문에, M 조건을 만족하는 j가 확인되면 j=3, j=4를 확인할 필요는 없다.

 

이를 투포인터로 바꿔보면, 

1. 맨 처음 st=0, en=0이 존재

2. arr[en] - arr[st] >= M이 될 때까지 en++

3. 조건을 만족하는 M을 찾으면 min을 갱신하고, st++ 후 다시 2번 진행

 

수도 코드

배열 정렬

while (st != N && en != N)
	if a[en] - a[st] >= <
    	min 갱신
        st++
    else
    	en++

 

코드

/*boj g5 2230 수 고르기 two pointer*/
#include <algorithm>
#include <iostream>
#define MAXN 100005
using namespace std;

int N, M;
int arr[MAXN];
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    for (int i = 0; i < N; i++)
        cin >> arr[i];

    int ans = 2000000000;
    sort(arr, arr + N);

    int st = 0;
    int en = 0;

    while (st != N && en != N) {
        if (arr[en] - arr[st] >= M) {
            ans = min(ans, arr[en] - arr[st]);
            st++;
        } else {
            en++;
        }
    }
    cout << ans << "\n";
}