큰 수 만들기 - kotlin
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.
문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.
주어진 숫자에서 특정 개수의 수를 제거했을때 최댓값을 찾아야하는 문제다.
단순히 작은 수를 찾아선 안되고, 순서내에서 작은수를 제거해야하므로 큰 수를 앞에 배치하고 앞에 존재하는 작은 수를 먼저 제거해야겠다고 생각했다.
풀이 과정
fun solution(number: String, k: Int): String {
var current = number
while (current.length != number.length - k) {
for (i in 0 until current.length - 1) {
if (current[i].toString().toInt() < current[i + 1].toString().toInt()) {
current = current.removeRange(i, i + 1)
break
}
}
}
return current
}탐욕법 알고리즘을 사용해서 주어진 길이가 되는 동안 앞에서부터 뒷 숫자가 더 큰 경우엔 그 수를 제거해줬다.
제한 길이가 1백만이라 10번과 12번 테스트케이스를 통과하지 못했고, 추가적으로 효율성을 고려해줘야 했다.
1차 수정
fun solution(number: String, k: Int): String {
val current = StringBuilder(number)
while (current.length != number.length - k) {
for (i in 0 until current.length - 1) {
if (current[i].code < current[i + 1].code) {
current.deleteAt(i)
break
}
// 반복 숫자에 대한 마지막 숫자 제거문
if (i == current.length - 2) current.deleteAt(current.length - 1)
}
}
return current.toString()
}효율성을 위해 subString을 사용하는 String에서 MutableList로 수정해봤지만, 10번을 해결할만큼 개선되지는 않았다. 혹시나 해서 StringBuilder을 사용해봤는데, 평균 15.00ms로 통과하던 케이스들이 0.04ms로 통과하며 엄청난 효율을 확인할 수 있었다..!
추가적으로 12번 테스트 케이스는 동일한 숫자에 대한 검증으로 마지막 index일시 마지막 숫자를 제거하는 코드로 무한 루프를 벗어날 수 있었다.
