백준 - 수 정렬하기2(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 : https://www.acmicpc.net/problem/2751

 

[문제 설명]

수를 정렬하라.

 

[접근 방법]

크기가 100만이므로 n^2의 시간복잡도를 가진 버블 정렬 같은 알고리즘은 사용하면 안 된다.

당연히 라이브러리로 구현되어 있는 정렬 메서드를 사용해도 충분히 통과가 가능하지만, 계수정렬을 구현해봤다.

일반적으로 합병정렬이나 퀵정렬은 자료 수가 n개 일 때 O(nlogn)이지만, 계수 정렬은 자료의 개수와 값의 범위에 따라 달려있다.

계수 정렬에서 자료의 크기가 n이고 범위가 m이면 O(n + m)이 시간 복잡도가 됩니다.

이 문제의 n의 크기는 100만이고, m의 범위는 절댓값이 100만 이하인 수이므로 200만이 됩니다.

따라서, 시간복잡도는 O(m)이 됩니다.

 

[Kotlin 코드]

fun main() {
    val output = StringBuilder()
    val n = readln().toInt()
    // O(n)
    val array = IntArray(n) { readln().toInt() }
    // O(n)
    var min = getMinOfArray(array)
    // if : 최솟값이 음수면 계산하기 편하게 양수로 만듬
    if (min < 0) min *= -1
    // O(n)
    val max = getMaxOfArray(array)
    // O(m)
    val dp = IntArray(max + min + 1)

    // O(n)
    array.forEach {
        dp[it + min]++
    }

    // 누적하기
    // O(m)
    for (i in 0 until dp.size - 1) {
        dp[i + 1] += dp[i]
    }

    // O(n)
    val sortedArray = IntArray(n)
    // O(n)
    for (i in array.size - 1 downTo 0) {
        val it = array[i]
        sortedArray[dp[it + min] - 1] = it
        dp[it + min]--
    }

    // O(n)
    sortedArray.forEach {
        output.append("$it\n")
    }
    println(output.deleteCharAt(output.length - 1))
}

fun getMinOfArray(array: IntArray): Int {
    var min = Int.MAX_VALUE
    array.forEach { min = min.coerceAtMost(it) }
    return min
}

fun getMaxOfArray(array: IntArray): Int {
    var max = Int.MIN_VALUE
    array.forEach { max = max.coerceAtLeast(it) }
    return max
}

이 문제를 기록하는 이유는 시간복잡도를 제대로 계산했는데도 시간초과가 났기 때문이다.

시간복잡도를 잘못 계산했거나, 코드를 실수했다고 생각하고 다시 봤는데도 잘못된 점이 없었다.

그래서, 출력문을 단순하게 매번 출력하기보다는 문자열의 덧붙이는 방식으로 코드를 수정했다.

출력문에서 시간이 은근 잡아먹는다는 사실을 알고 있긴 했었지만, 실제로 출력문 하나 때문에 시간 초과가 난 적이 없어서 순간 당황스러웠다.

아무튼 출력문도 신경 쓰자.