[BOJ] 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이 된다.

- 시간 제한 : 2초
- 메모리 제한 : 128MB

입력

첫째 줄에 두 정수 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

접근 방법

두 수의 차이 중 M 이상이면서 최소를 구하는 문제입니다. 배열로 받은 입력에서 두 수를 나타내는 pointer들을 설정하여 배열을 탐색하며 구할 수 있으므로 two pointers를 이용하여 문제를 해결할 수 있습니다.

하나의 pointer는 작은 수를 가르키게하고 다른 pointer는 큰 수를 가르키게하여 차이가 M 이상이면 작은 수를 가르키는 pointer가 더 큰 수를 가르키게 하고, M보다 크면 큰 수를 가르키는 pointer가 더 큰 수를 가르키게 하여야 합니다. 그러기 위해서는 먼저 배열을 정렬하여야 합니다.

// 두 수의 차이가 m 이상 일 경우
if (diff >= m) {
    // result보다 작으면 result를 update
    if (diff < result) {
        result = diff
    }

    // 차이가 m과 같으면 더이상 탐색은 무의미
    if (diff == m) return

    // 차이가 더 작아야 하므로 left가 더 큰 수를 가르키게 한다.
    ++left
} else {
    // 더 이상 차이를 구할 수 없으므로 return
    if (right == n - 1) return

    // 차이가 더 커야 하므로 right가 더 큰 수를 가르키게 한다.
    ++right
}

이 방법으로 문제를 해결하면 정렬에 O(N log N), two pointers 이용하여 탐색에 O(N)의 시간을 소요하여 문제를 해결할 수 있습니다.

코드

import java.util.*
import java.lang.*

var n = 0
var m = 0

var _numbers: IntArray? = null
val numbers get() = _numbers!!

var result = 2_000_000_000

fun main() {
    input()
    func()
    println(result)
}

fun input() {
    val sc = Scanner(System.`in`)

    n = sc.nextInt()
    m = sc.nextInt()

    _numbers = IntArray(n) {
        sc.nextInt()
    }

    sc.close()
}

fun func() {
    Arrays.sort(numbers)

    var left = 0 // 작은 수를 가르킬 pointer
    var right = 1 // 큰 수를 가르킬 pointer

    while (true) {
        val diff = numbers[right] - numbers[left]

		// 두 수의 차이가 m 이상 일 경우
        if (diff >= m) {
        	// result보다 작으면 result를 update
            if (diff < result) {
                result = diff
            }

			// 차이가 m과 같으면 더이상 탐색은 무의미
            if (diff == m) return

			// 차이가 더 작아야 하므로 left가 더 큰 수를 가르키게 한다.
            ++left
        } else {
        	// 더 이상 차이를 구할 수 없으므로 return
            if (right == n - 1) return

			// 차이가 더 커야 하므로 right가 더 큰 수를 가르키게 한다.
            ++right
        }
    }
}