알고리즘/백준

[백준][C++] 2230: 수 고르기

KANTAM 2023. 11. 29. 19:50

문제

 

2230번: 수 고르기

N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어

www.acmicpc.net

풀이

정렬, 두 포인터 문제이다. 

 

  • 입력받은 수열을 정렬한다. 
  • start와 end를 0에서부터 시작한다. 
  • start와 end에서의 수의 차이가 M이상이라면 답을 갱신한다. 차이를 더 줄이기 위해 start를 증가시킨다.
  • 미만이라면 차이를 더 늘리기 위해 end를 증가시킨다.

코드

#include <iostream>
#include <algorithm>
#include <climits>

using namespace std;

int nums[100000];

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

    int N, M;
    cin >> N >> M;

    // 수열을 입력받고 정렬한다.
    for (int i = 0; i < N; ++i)
    {
        cin >> nums[i];
    }
    sort(nums, nums + N);

    int start = 0;
    int end = 0;
    int answer = INT_MAX;
    while (start <= end && end < N)
    {
        int current = nums[end] - nums[start];

        // start와 end의 차이가 M이상이라면 답을 갱신한다. 
        // 차이를 더 줄이기 위해 start를 증가시킨다.
        if (current >= M)
        {
            answer = min(answer, current);
            start++;
        }
        // 미만이라면 차이를 더 늘리기 위해 end를 증가시킨다.
        else
        {
            end++;
        }
    }

    cout << answer;

    return 0;
}