Kotlin Boxing Type 쓰지 마세요 체질이라는게바뀝니다

240409 내용 추가

이 글에서 설명한 시간 측정 차이는 프로그래머스 채점 오류라고 생각합니다. 아래 글을 참고해주세요.

https://dodobest.tistory.com/96

프로그래머스 시간 측정 오류와 H-Index 문제

 

 

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

프로그래머스 문자열 내림차순으로 배치하기 문제를 풀어보며, String을 다룰 때 어떻게 하면 시간을 단축할 수 있는지 알아보겠습니다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/12917

프로그래머스

 

 

 

String을 빠르게 다루는 방법

String을 정렬해야 한다면 아래의 순서를 따른다.

1. charArray로 변환한다.
2. Arrays.sort 함수를 이용해 정렬한다.

 

arr.sort의 내부 코드를 확인해보면 동일하게 Arrays.sort 함수를 이용하고 있으나, 시간 차이가 많이난다.

디컴파일된 코드를 확인해보면 arr.sort는 Kotlin의 collection boxing type을 사용하고 있는데, 이 과정에서 오버헤드가 발생하는 것으로 추정된다.

 

 

 

CharArray를 문자열로 바꿔야 한다면 String 함수를 이용한다.

joinToString은 내부적으로 StringBuilder를 이용해 문자열을 생성한다.

concatToString 함수는 내부적으로 String 함수를 호출하나, 디컴파일 된 코드를 보면 박싱타입을 사용하고 있다.

 

 

import java.util.Arrays
 
class Solution {
    fun solution(s: String): String {
        val arr = s.toCharArray()
        Arrays.sort(arr) // 평균 0.5ms
//        arr.sort() // 평균 10ms
 
        val sb = StringBuilder(String(arr, 0, arr.size)) // 평균 0.5ms
//        val sb = StringBuilder(arr.joinToString("")) // 평균 15~18ms
//        val sb = StringBuilder(arr.concatToString()) // 평균 6~10ms
 
        return sb.reverse().toString()
    }
}

 

 

처음에 시도한 방법

Ascii 코드 값, IntArray, StringBuilder를 이용하면 빠를 것으로 생각했으나, 15ms에 근접하는 시간이 소요됐다.

 

class Solution {
    fun solution(s: String): String {
        val sb = StringBuilder()
        val chars = IntArray(52)
 
        for (c in s) {
            val num = if (c >= 'a') {
                c - 'a' + 26
            } else {
                c - 'A'
            }
            chars[num]++
        }
 
        for (i in chars.lastIndex downTo 0) {
            val count = chars[i]
            if (count == 0) {
                continue
            }
            val char = charsCheatSheet[i]
            for (dummy in 0 until count) {
                sb.append(char)
            }
        }
        return sb.toString()
    }
 
    companion object {
        private val charsCheatSheet = charArrayOf('A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',)
    }
}

 

 

참고자료

https://ilmiodiario.tistory.com/53

[프로그래머스] level1. 문자열 내림차순으로 배치하기 (자바 JAVA)