[Kotlin] 백준 20551 : Sort 마스터 배지훈의 후계자

문제 링크

20551번: Sort 마스터 배지훈의 후계자

---

문제 해설

사용 알고리즘 : 이진탐색

문제 자체는 단순히 배열을 정렬한 후 M번에 걸쳐서 해당 요소의 첫 위치를 찾아내면 되는 문제이다. N과 M이 작다면 그냥  \(O(N\times M)\)인 indexOf()로 해결할 수 있지만 N과 M이 각각 최대 20만이기 때문에 이 방법은 시간초과가 발생한다.

 

코틀린에서는 이진탐색을 수행하는 binarySearch() 메소드가 존재하지만 이 메소드는 찾고자 하는 값을 발견하면 가장 첫 위치가 아니라 이진 탐색중에 발견한 위치를 바로 반환하기 때문에 사용할 수 없다.

 

때문에 직접 이진탐색을 위한 메소드를 구현해야 하는데 이는 어렵지 않다. 기본으로 구현되어 있는 binarySearch() 메소드에서 값을 찾았을 때 바로 위치를 반환하지 않고 계속 이진탐색을 수행하도록 하면 된다.

 

마지막에 반환할 때 발견한 위치의 요소가 찾고자 하는 값과 같다면 발견한 위치를 반환하면 된다.(이 때, ArrayIndexOutOfBoundsException을 방지하기 위한 예외 처리를 해줘야 한다.) 그렇지 않은 경우에는 -1을 반환한다.

 

속도는 느리지만 Map을 사용하는 방법도 있다. 배열을 정렬한 후 배열을 순회하면서 Map에 요소를 key로, 위치를 value로 저장하면 된다. 이 때, 해당 key가 Map에 존재하지 않는 경우에만(= 해당 key의 value가 null일 때만) value를 설정해주면 된다. 이후 Map에서 값을 꺼내면서 값이 없는 경우에는 -1을 출력하면 된다.

Code

이진 탐색

fun main() = with(System.`in`.bufferedReader()) {
    val bw = System.out.bufferedWriter()
    val (n, m) = readLine().split(' ').map { it.toInt() }
    val arr = IntArray(n) { readLine().toInt() }.sortedArray()
    repeat(m) { bw.write("${arr.binarySearch(readLine().toInt())}\n") }
    bw.close()
}

private fun IntArray.binarySearch(target: Int): Int {
    var start = 0
    var end = size

    while (start < end) {
        val mid = (start + end) / 2
        if (this[mid] >= target) end = mid
        else start = mid + 1
    }

    return if (start < size && this[start] == target) start else -1
}

 

Map

fun main() = with(System.`in`.bufferedReader()) {
    val bw = System.out.bufferedWriter()
    val (n, m) = readLine().split(' ').map { it.toInt() }
    val map = IntArray(n) { readLine().toInt() }.sortedArray().run { HashMap<Int, Int>().apply { forEachIndexed { i, v -> get(v) ?: put(v, i) } } }
    repeat(m) { bw.write("${map[readLine().toInt()] ?: -1}\n") }
    bw.close()
}

두 방법의 속도 차이

아래가 이진 탐색을 사용한 코드, 위가 Map을 사용한 코드이다. 확실히 이진탐색이 더 빠른 것을 볼 수 있다.