(골드 5)백준 2230: 수 고르기

문제

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

예를 들어 수열이 {1, 2, 3, 4, 5}라고 하자. 만약 M = 3일 경우, 1 4, 1 5, 2 5를 골랐을 때 그 차이가 M 이상이 된다. 이 중에서 차이가 가장 작은 경우는 1 4나 2 5를 골랐을 때의 3이 된다.

입력

첫째 줄에 두 정수 N, M이 주어진다. 다음 N개의 줄에는 차례로 A[1], A[2], …, A[N]이 주어진다.

출력

첫째 줄에 M 이상이면서 가장 작은 차이를 출력한다. 항상 차이가 M이상인 두 수를 고를 수 있다.

---

핵심

0. N, M을 입력 받고 N개의 수를 입력 받는다.

1. N개의 수 중 두개의 수를 골라서 뺀 수의 절댓값이, M보다 크거나 같다는 조건을 성립할 경우, 성립하는 수 중 가장 작은 값을 출력한다.

---

코드

#include <iostream>
#include <queue>
#include <vector>
#include <set>
#include <unordered_set>
#include <map>
#include <stack>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;

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

    int n, m;
    cin >> n >> m;

    vector<int> v;
    for (int i = 0; i < n; i++)
    {
        int temp;
        cin >> temp;
        v.push_back(temp);
    }

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

    int left = 0,
        right = 1;

    int gap = 2000000000;
    while (left < n - 1)
    {
        int sub = v[right] - v[left];

        if (sub < gap && sub >= m)
        {
            gap = sub;
        }

        // right가 끝일경우
        if (right == n - 1)
        {
            left++;
        }
        // left가 끝이거나 뺸 값이 m보다 작으면
        else if (left + 1 == right || sub < m)
        {
            right++;
        }
        else
        {
            left++;
        }
    }

    cout << gap;

    return 0;
}

---

풀이

이번 문제는 전형적인 투포인터 문제였다.

1. 수 리스트를 받아 정렬한 후, left, right 두개의 인덱스를 설정한다.

2. v[right] - v[left]로 두개의 수의 차를 구해 m보다 크거나 같으며 gap보다 작을 경우 gap을 갱신해준다.

3-1. left가 right - 1이거나 right가 n-1 인 경우 각 반대 인덱스를 + 1 한다. (각 인덱스가 더 증가할 수 없는 위치)

3-2. 위 경우(3-1)가 아닌 경우 sub 값이 m보다 작은 경우 right를 증가시킨다. (더 큰 sub 탐색)

3-3. 위 경우(3-2)가 아닌 경우 left를 증가시킨다. (더 작은 sub 탐색)