[2230] 수 고르기

문제 링크 : https://www.acmicpc.net/problem/2230

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$이상인 두 수를 고를 수 있다.

제한

시간 제한	메모리 제한
2sec	128MB

• $1 \leq N \leq 100\,000$
• $0 \leq M \leq 2\,000\,000\,000$
• $0 \leq \lvert A[i] \rvert \leq 1\,000\,000\,000$

---

풀이

두 수를 골랐을 때 그 차이가 항상 $M$ 이상이 될 수 있는 값들을 찾아야 한다. 수의 개수가 10만개이므로 모든 수에 대해 계산하는 $O(N^2)$으로는 시간초과가 발생한다. 탐색 범위를 줄여나가야한다.

투 포인터를 활용하면 탐색 시간을 $O(N)$으로 줄일 수 있다. 하지만 투포인터를 활용하기 위해선 정렬과정이 필요하므로, 실질적으로 시간은 $O(N \log N)$이 소요된다.

우선 모든 수를 오름차순으로 정렬해준다. 그리고 가장 왼쪽의 값을 $a$, 그 다음 값을 $b$라고 하자. 이후 아래와 같은 탐색과정을 거친다.

• 두 수의 차이를 비교한다 ($d = b - a$)
  • 두 수의 차이 $d \geq M$이라면, 값을 기록하고 $a$를 다음 수로 옮긴다
  • 두 수의 차이 $d < M$이라면, $b$를 다음 수로 옮긴다

이렇게 하면 $b$가 마지막에 도착하면 더 이상 탐색할 필요가 없다. 이 방법이 가능한 이유는, 만약 $d \geq M$이라면 $b$를 늘려봤자 새로 계산되는 차이 $D \geq d$이기 때문에 정답이 될 수 없다. 이 경우 $a$를 한칸 전진시켜 $D < d$가 되도록 해야한다. 반대로 $d < M$이라면 $a$를 늘려봤자 새로 계산되는 차이 $D < d < M$이기 때문에 이 역시 정답이 될 수 없다. 이 경우 $b$를 한칸 전진시켜 $D > d$가 되도록 해야한다. 즉 차이를 계산할 때마다 $a$ 또는 $b$가 한칸씩 전진하게 되고, 최대 $2N$번의 연산을 통해 우리가 원하는 답을 찾을 수 있게 된다.

• 참고 알고리즘 : 투 포인터

코드

사용 언어 : C

최종 수정일 : 2024 / 2 / 27

#include <stdio.h>

#define MAX_IDX 100000
const int INF = (int)(2e9 + 1);

int arr[MAX_IDX];
int n;
int ret = INF;
int m;

int ascend(int* a, int* b) { return *a > *b; }
#define min(a, b) (((a) > (b)) ? (b) : (a))

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; ++i) {
        scanf("%d", arr + i);
    }
    qsort(arr, n, sizeof(int), ascend);

    int left = 0, right = 0;
    while (right < n) {
        if (arr[right] - arr[left] >= m) {
            ret = min(ret, arr[right] - arr[left]);
            ++left;
        } else {
            ++right;
        }
    }

    printf("%d", ret);
    return 0;
}