[Programmers] 가장 큰 수

 

🔒 문제

 

💭 생각의 흐름

1. 맨 첫글자로 group을 나누어 9..0 역순으로 훑는다.

 

2. 각 라운드를 돌며 중복 없이 가장 큰수가 하나 나올때 마다 이어붙인다.

roundArray = [3, 34, 3411, 3434, 3413, 345]

1라운드 : 3 3 3 3 3 3 3
2라운드 : 3 4 4 4 4 4
3라운드 : 3 3 1 3 1 5
4라운드 : 3 4 1 4 3
...

 

😵‍💫 실수

1. 위 방법에서 중복이 있을 경우 해당 숫자만 후보로 남기고 라운드를 또 따로돌려야한다.

-> 재귀를 써야함.

2. 모든 숫자가 0이 올 경우 출력은 0이다. ex) [0, 0, 0, 0] -> 0

(※ 결과를 string으로 반환할 뿐 어쨌든 가장 큰 정수 변환하여 출력해야한다.)

 

🔐 잘못된 풀이 (Kotlin)

package max_number

import java.lang.StringBuilder
import java.util.*

/*
========================================
가장먼저 큰 수가 나오는 넘을 쏟아내면 된다.
동점자 군을 묶는다. 같은애들끼리의 리그이다.
동점자 리그는 다시 첫자리 부터 시작임. (뒷자리 없을 경우)
수식 표현: index % it.length (★)
=======================================
 */
class Solution {
    fun solution(numbers: IntArray): String {
        // 맨 첫자리를 각 군으로 나눔 (첫자리 9 ~ 0) 0이면 할 게 없음
        val stringArray = numbers.map { it.toString() }
        val map = stringArray.groupBy { it[0] }
        val stringBuilder = StringBuilder()
        for (key in map.keys.sorted().reversed()) {
            // round 시작
            val roundArrayList = map[key]!! as ArrayList<String> // 이미 여기서 라운드 배열이 담김
            var index = 0
            while (roundArrayList.isNotEmpty()) {
                val positionArrayList = Array<String>(roundArrayList.size){index-> roundArrayList[index % roundArrayList[index].length]}
                // 각 자리수는 모인상황 (positionArrayList 모임)
                val maxValue = positionArrayList.maxOf { it }
                val occurrences = positionArrayList.count(){it == maxValue} // 최대값 갯수
//                독보적으로 큰놈
                if (occurrences == 1) {
                    val targetIndex = positionArrayList.indexOf(maxValue)
                    stringBuilder.append(roundArrayList[targetIndex])
                    roundArrayList.removeAt(targetIndex)
                }
                index++
                    // 문제는 겹치기만했을 때임.. 무한 loop 끝나지 않음 34 vs 3434
                    // 뭐 먼저하든 상관 없긴함 ㅎㅎ
            }
        }
        return stringBuilder.toString()
    }
}

fun main() {
    println(Solution().solution(arrayOf(6, 61, 56, 10, 102, 24, 2).toIntArray()))
}

 

 

'정렬..'?

C를 제외한 어느언어든 기본 자료구조에 대한 정렬은 모두 지원하고 정렬시 사용할 compare 함수를 정의할 수 있단 사실을 떠올렸다.

compare (우선순위 구분 함수)는 다음과 같다.

앞 & 뒤 숫자를 이어붙이고 더 큰놈을 먼저오게한다.

 

🔑 풀이 (Kotlin)

import java.lang.StringBuilder

class Solution2 {
    fun solution(numbers: IntArray): String {
        // 모든 숫자 0으로 들어오면 1번 0 하고 끝냄. (0을 연속한 수는 자연수가 아님)
        if (numbers.all { it == 0 }) return "0"
        //        첫 글자로 나눔
        val map = numbers.map{it.toString()}.groupBy { it[0] }
        val stringBuilder = StringBuilder()
        for (key in map.keys.sorted().reversed()) {
            with(map[key]!!){
                sortedWith(Comparator<String> { o1, o2 ->
                    when {
                        o1 + o2 < o2 + o1 -> 1
                        o1 + o2 == o2 + o1 -> 0
                        else -> -1
                    }
                }).forEach { stringBuilder.append(it) }
            }
        }
        return stringBuilder.toString()
    }
}

.... 그냥 문자열간 대소비교만 하면 되는 ㅈ밥 문제였는데..

ㅈ밥은 나였다.

 

 

최적화 코드

comapreTo는 앞, 뒷놈의 대소비교를 하는데

더 작으면 -1, 같으면 0 , 크면 1이라 default는 오름차순이다.

따라서 내림차순을 위해서는 o1, o2 (앞, 뒷) 놈의 순서를 바꿔서 조합해주면 된다.

o1, o2 -> (o2+o1).compareTo(o1+o2)