[Algorithm] 프로그래머스 가장 큰 수(1) - Kotlin

프로그래머스의 정렬 문제 중 Level 2문제인 가장 큰 수에 대해 정리해보려 한다.

코딩 테스트 연습 - 가장 큰 수 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 가장 큰 수

 

문제의 내용을 요약하면

주어진 배열의 객체를 모두 한 번씩 사용해 만들 수 있는 가장 큰 수를 구하는 문제이다.

numbers	return
[6, 10, 2]	"6210"
[3, 30, 34, 5, 9]	"9534330"

 

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

처음에 이 문제를 보고 간단하게 생각해서 아래와 같은 방법으로 구현했다.

 

1. numbers 객체의 첫 번째 자릿수를 확인해 9부터 임시 리스트에 저장 (이때 기존 리스트에서 저장된 객체를 제거)

 

2. 임시로 저장된 리스트의 객체를 각 각 4자리 수(1 -> 1111,  12 -> 1212,  123 -> 1231)로 맞춰주고 그 값을 비교해 내림차순으로 정렬해준다. (4자리 수로 맞추는 이유는 1,000이 포함되기 때문에 1000을 예외 처리할 거 아니면 1000, 100 이 존재하는 경우 "1000100"으로 출력되는 불상사가 생길 수 있다.)

 

3. 정렬이 끝나면 answer에 그 값들을 String 형태로 더함

 

4. 임시 리스트를 비워주고 1, 2, 3번을 i가 1이 될 때까지 반복

 

5. 기존 리스트가 아직 남아있는 경우 -> 0인 값이 남아 있는 경우로 answer의 뒤에 붙여준다.

 

6. answer가 0으로 시작되는 문자열이라면 "0" 

 

fun mySolution(numbers: IntArray): String{
    var answer = ""
    val originNumbers = ArrayList(numbers.toList())
    val tmpNumbers = arrayListOf<Int>()
    // 9부터 1까지 리스트 별로 분리
    for(i in 9 downTo 1){
        var j = 0
        while(j < originNumbers.size){
            // 객체의 첫번째 자릿수가 i와 같다면
            if(i==getFirst(originNumbers[j])){
                // 임시 리스트에 저장하고 기존 리스트에서 삭제 시켜준다.
                tmpNumbers.add(originNumbers[j])
                originNumbers.removeAt(j--)
            }
            j++
        }
        tmpNumbers.sortedWith(Comparator{ n1, n2 ->
            if(makeFourDigit(n1) > makeFourDigit(n2)) -1
            else 1
        }).forEach {
            answer += it.toString()
        }
        tmpNumbers.clear()
    }
    // 리스트 안에 0만 남아 있는 경우
    if(originNumbers.isNotEmpty()) {
        while(originNumbers.size>0){
            answer += originNumbers[0]
            originNumbers.removeAt(0)
        }
    }

    // 0으로 시작하는 문자열이면 0을 출력 아니면 answer을 출력
    return if(answer.matches("0*".toRegex())) "0" else answer
}

// 첫 번째 자릿수 꺼내는 메서드
fun getFirst(number: Int): Int{
    return if(number<10) number
    else{
        if(number/10>9) getFirst(number/10)
        else number/10
    }
}

// 4자리 숫자로 만드는 메서드
fun makeFourDigit(number: Int): Int{
    val tmpNumber = number.toString()
    return if(tmpNumber.length < 4) makeFourDigit((tmpNumber + tmpNumber).toInt())
    else tmpNumber.substring(0,4).toInt()
}

 

하지만 결과는 참혹할 정도의 런타임 에러... 

메모리의 경우 다른 성공 케이스에 비해 비교적 많이 소모하는 편이지만 그래도 이쪽 문제인 거 같지는 않고 시간 복잡도 때문인 거 같은데, for문, while문, 재귀 함수, sort 등 비교해서 너무 많은 반복문이 들어가는 것 때문에 그런 거 같다. 

 

그래도 나름 고민해서 만든 예제인데, 바로 지우고 다시 하긴 아까워서 일단 결과 값이 맞는지 성공한 분의 코드를 이용해 여러 가지 상황의 테스트 케이스를 추가하고 결과 값들을 비교해 보았다.

 

성공 케이스

fun solution2(numbers: IntArray): String {
    var answer = ""
    //문자열로 변환 및 마지막 자리를 pad로 채워 정렬
    numbers.sortedByDescending {
        it.toString().padEnd(4,'%').replace("%",it.toString())
    }.forEach{
        answer += it
    }
    //정규식 사용하여 00000...을 0으로 변환
    var patten = "[1-9]".toRegex()
    if(!patten.containsMatchIn(answer)){
        answer = "0"
    }
    return answer
}

 

비교 결과

fun main() {
    println("가장 큰 수")

    val numbers1 = intArrayOf(6, 10, 2, 30, 345, 9, 99, 94, 12, 53, 36, 7, 432, 666, 324, 175, 279, 235, 10, 11, 5, 3)
    val numbers2 = intArrayOf(3, 30, 34, 5, 9)
    val numbers3 = intArrayOf(6, 10, 2)
    val numbers4 = intArrayOf(0, 0, 0, 0, 0, 0)
    val numbers5 = intArrayOf(3, 30, 34, 5, 9, 4, 40, 42)
    val numbers6 = intArrayOf(12, 121)
    val numbers7 = intArrayOf(0,0,70)
    val numbers8 = intArrayOf(1000,100)
    val numbers9 = intArrayOf(21, 212)

    println("결과")
    println("solution2 numbers1: ${solution2(numbers1)}, mySolution numbers1: ${mySolution(numbers1)}\n " +
            "${(mySolution(numbers1)==solution2(numbers1))}")
    println()
    println("solution2 numbers2: ${solution2(numbers2)}, mySolution numbers2: ${mySolution(numbers2)}\n " +
            "${(mySolution(numbers2)==solution2(numbers2))}")
    println()
    println("solution2 numbers3: ${solution2(numbers3)}, mySolution numbers3: ${mySolution(numbers3)}\n " +
            "${(mySolution(numbers3)==solution2(numbers3))}")
    println()
    println("solution2 numbers4: ${solution2(numbers4)}, mySolution numbers4: ${mySolution(numbers4)}\n " +
            "${(mySolution(numbers4)==solution2(numbers4))}")
    println()
    println("solution2 numbers5: ${solution2(numbers5)}, mySolution numbers5: ${mySolution(numbers5)}\n " +
            "${(mySolution(numbers5)==solution2(numbers5))}")
    println()
    println("solution2 numbers6: ${solution2(numbers6)}, mySolution numbers6: ${mySolution(numbers6)}\n " +
            "${(mySolution(numbers6)==solution2(numbers6))}")
    println()
    println("solution2 numbers7: ${solution2(numbers7)}, mySolution numbers7: ${mySolution(numbers7)}\n " +
            "${(mySolution(numbers7)==solution2(numbers7))}")
    println()
    println("solution2 numbers8: ${solution2(numbers8)}, mySolution numbers8: ${mySolution(numbers8)}\n " +
            "${(mySolution(numbers8)==solution2(numbers8))}")
    println()
    println("solution2 numbers9: ${solution2(numbers9)}, mySolution numbers9: ${mySolution(numbers9)}\n " +
            "${(mySolution(numbers9)==solution2(numbers9))}")
    println()
}

비교 결과를 보면 일단 결과 값들은 정확한 거 같다.

 

성공 케이스를 보면서 시간 복잡도에 대한 힌트를 얻었는데, for, sort 총 두 번 반복문을 이용하고 정규화를 통해 0인 경우의 예외처리를 하는 방식으로 이루어졌음을 확인했다.

 

그렇다면 위에서 만든 구문을 최소화해보기로 했다. 일단 1번 2번 구문 제거하니 8, 9번 테스트 결과는 통과했고 나머지는 런타임 에러가 떴고 이를 풀기 위해선 재귀 함수 makeFourDigit를 제거하고 대체할 구문을 생각해야 할 거 같다.

 

fun newMySolution(numbers: IntArray): String{
    var answer = ""

    numbers.sortedWith(Comparator { n1, n2 ->
        if(makeFourDigit(n1) > makeFourDigit(n2)) -1
        else 1
    }).forEach {
        answer += it.toString()
    }

    return if(answer.matches("0*".toRegex())) "0" else answer
}

// 4자리 숫자로 만드는 메서드
fun makeFourDigit(number: Int): Int{
    return if(number==0) number
    else{
        val tmpNumber = number.toString()
        if(tmpNumber.length < 4) makeFourDigit((tmpNumber + tmpNumber).toInt())
        else tmpNumber.substring(0,4).toInt()
    }
}

 

 

순서상의 두 숫자를 앞 뒤로 String 상태에서 더한 뒤 다시 Int형으로 변환시켜 비교하여 더 큰 수를 앞으로 보내는 식으로 수정하였으나 아래처럼 몇 가지 부분에서 런타임 에러가 뜨면서 실패하였다. 성공 케이스와 비교해본 결과 값은 정확히 나오는 것은 확인했다. 다만 내가 생각한 방식의 시간 복잡도나 메모리 사용 여부가 상당히 아쉬웠다... 결과적으로 가장 좋은 방법은 String 값으로 변환하여 앞 뒤로 더한 뒤 compareTo로 비교해서 정렬하는 게 가장 좋은 방법인 거 같다. 

fun newMySolution(numbers: IntArray): String{
    var answer = ""

    numbers.sortedWith(Comparator { n1, n2 ->
        compareToNumbers(n1, n2)
    }).forEach {
        answer += it.toString()
    }

    return if(answer.matches("0*".toRegex())) "0" else answer
}

fun compareToNumbers(n1: Int, n2: Int): Int{
    val tmpN1 = n1.toString()
    val tmpN2 = n2.toString()
    return if((tmpN1 + tmpN2).toInt() > (tmpN2 + tmpN1).toInt()) -1
    else 1
}

 

일단 이번 풀이는 여기까지 하고 다음번에는 다른 분들이 만든 성공한 케이스들 중 2개 정도 뽑아서 정리해보려 한다.