[BOJ] 2230. 수 고르기 (C++)

문제

N개의 정수로 이루어진 수열 중 두 수를 골랐을 때(같은 수일 수도 있음) 차이가 M이상이면서 제일 작은 경우를 구하기

생각할 것

배열을 정렬하고, 투포인터를 이용해보기

start, end를 가장 처음에 둔다. (같은 수일 수도 있으므로)

차이가 M보다 작으면 키우기 위해 end를 옮기고, 크면 start를 옮긴다.

res의 초기 값을 res[N-1] - res[0]으로 설정해야한다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    int N, M;
    cin >> N >> M;
    vector<int> vec(N);
    for (int i = 0; i < N; i++) {
        cin >> vec[i];
    }

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

    int start = 0, end = 0, res = vec[N - 1] - vec[0];
    while (start < N && end < N) {
        int diff = vec[end] - vec[start];
        if (diff < M) { // 차이가 M보다 작으면 end를 늘리기
            end++;
        } else { // 크면 뺴는 수를 늘리기
            start++;
            res = min(res, diff);
        }
    }

    cout << res;

    return 0;
}