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

제한

• 1 ≤ N ≤ 100,000
• 0 ≤ M ≤ 2,000,000,000
• 0 ≤ |A[i]| ≤ 1,000,000,000

===

문제 풀이

우선 입력값들이 굉장히 커서 BigInt 처리를 해주었다.

const [n, m] = input[0].split(' ').map(BigInt);
const arr = input
    .slice(1)
    .map(BigInt)
    .sort((a, b) => {
        if (a < b) return -1;
        return 1;
    });

두 수를 골랐을 때 차이가 m 이상인 경우들은 b-a>=m 이상인 경우를 찾으면 되는 것이다.

이는 곧 b>=a+m 을 구하는 것과 같은 것이다.

따라서 배열을 오름차순 정렬한 뒤 인덱스 0부터 마지막 이전까지의 수를 pivot으로 고정한 뒤에

pivot 다음 인덱스에 위치한 요소가 arr[pivot]+m 이상이 되는 경우 중 가장 작은 차이를 찾으면 된다.

이때 다음 인덱스부터 하나하나 검사하는 것은 곧 N^2 수를 유발하여 시간 초과가 발생.

따라서 NLogN 방식을 취하는 이진 탐색을 진행한다.

const binary = (start) => {
    const target = arr[start] + m;
    let s = start + 1n;
    let e = n - 1n;
    let result;
    while (s <= e) {
        const mid = (s + e) / 2n;
        if (arr[mid] >= target) {
            result = mid;
            e = mid - 1n;
        } else {
            s = mid + 1n;
        }
    }
    return result;
};

 

만약 pivot 요소와의 차이가 m 이상이 나는 경우가 없다면 result는 undefined를 리턴하여 이 경우는 패스해주고

조건을 만족한다면 가장 작은 diff를 찾으면 된다.

let answer = Infinity;

for (let i = 0n; i < n - 1n; i += 1n) {
    const idx = binary(i);
    if (idx === undefined) continue;

    const num = arr[idx] - arr[i];
    if (answer > num) answer = num;
}

console.log(answer.toString());

정답 코드

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const [n, m] = input[0].split(' ').map(BigInt);
const arr = input
    .slice(1)
    .map(BigInt)
    .sort((a, b) => {
        if (a < b) return -1;
        return 1;
    });

// b-a >=m
// a+m <=b

const binary = (start) => {
    const target = arr[start] + m;
    let s = start + 1n;
    let e = n - 1n;
    let result;
    while (s <= e) {
        const mid = (s + e) / 2n;
        if (arr[mid] >= target) {
            result = mid;
            e = mid - 1n;
        } else {
            s = mid + 1n;
        }
    }
    return result;
};

let answer = Infinity;

for (let i = 0n; i < n - 1n; i += 1n) {
    const idx = binary(i);
    if (idx === undefined) continue;

    const num = arr[idx] - arr[i];
    if (answer > num) answer = num;
}

console.log(answer.toString());