kotlin) Array<Int> vs IntArray

 

아래 문제를 코틀린 언어로 풀다가 시간초과가 발생했다.

https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

 

시간 초과가 발생한 코드는 아래 코드다 

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.sqrt

fun main()
{
    val sc = Scanner(System.`in`)
    var N = sc.nextInt()
    var M = sc.nextInt()
    val trees = Array<Long>(N) {0}

    var left = 0L
    var right = 0L
    for(i in 0 until N)
    {
        trees[i] = sc.nextLong()
        right = Math.max(right, trees[i])
    }

    var answer = 0L
    Arrays.sort(trees)

    while(left <= right)
    {
        var mid = (left + right) / 2

        var sum = 0L
        for(i in 0 until N)
        {
            if(trees[i] > mid) sum += (trees[i] - mid)
        }

        if(sum < M)
        {
            right = mid - 1
        }
        else
        {
            left = mid + 1
            answer = mid
        }
    }
    print(answer)
}

 

이분탐색을 이용해 풀었는데 위의 코드에서 11번째 줄  Array<Long>을 LongArray로 바꿔줬더니 통과했다.

 

찾아보니 코틀린의 IntArray, LongArray는 박싱을 안하는 자바로 따지면 int[], long[]과 같고 Array<Int>, Array<Long>은 자동 박싱이 진행되는 Integer[] 같은것이라고 한다.

 

코드를 수정해본 결과 Array<Long> 사용시 정렬할때 LongArray를 정렬하는것 보다 훨씬 많은 시간을 사용하는것 같다. 

 

찾아본 결과 Arrays.sort는 정렬 대상이 Primitive type (int, long 등) 인 경우 DualPivotQuickSort 라는 정렬방식으로 정렬을하고, object type인 경우 timsort 라는 방식으로 정렬을 한다고 한다.

이 두 정렬방식이 어떤식으로 다른지는 찾아보지 않았지만 아마 정렬방식의 차이 때문에 Array<Long> 으로 선언했을때 시간초과가 난것같다.

 

 

 

https://stackoverflow.com/questions/45090808/intarray-vs-arrayint-in-kotlin