[프로그래머스/programmers] 가장 큰 수 kotlin

1. 문제 설명

 

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

 

2. 제한 사항

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

3. 입출력 예

 

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

----------------------------------------------------------------------------------------------------------------

 

 

4. 알고리즘 분석

 

먼저 numbers의 각각의 원소를 문자열로 바꿔서 비교해서 붙였을 때 가장 큰 수가 나오게 되는 경우를 생각해봐야 합니다.

 

첫번째로 두 원소의 자리수가 같다면 더 큰 값을 앞으로 오게끔 정렬을 시키면 됩니다.

ex) 6,2 같은 경우 6이 2보다 크므로 앞으로 정렬시킵니다.

 

두번째로 두 원소의 자리수가 다르다면 두 원소를 번갈아가며 자리를 바꿔 붙여서 더 큰 값을 앞으로 정렬 시킵니다.

ex) 6,10 같은 경우 두 원소를 붙여보면 610 , 106 중에서 610이 더 크기 때문에 6을 10 앞에 정렬 시킵니다. 

 

5. 코드로 구현

class Solution {
    fun solution(numbers: IntArray): String {
        
        var result : String = ""
        
        var sortArray = numbers.map{ it.toString()}
                               .sortedWith(Comparator{back , front -> 
                               when {
                                   back.length == front.length -> front.compareTo(back)
                                   else -> (front+back).compareTo(back+front)
                               }
                             })
        if(sortArray[0] == "0") return "0"
        sortArray.forEach {
            result += it
        }
        return result
    }
}

 

sortedWith 메서드를 통해서 Comparator 를 구현하여 내가 원하는 조건에 맞게끔 sort 를 시킵니다.

 

정렬 후에 처음숫자가 0 으로 시작하면 가장 큰 수는 0 이므로 바로 return "0" 시키도록 예외 처리 합니다.

 

Comparator의 작동 되는 원리가 궁금하신분들을 위해서 Debug 모드로 설명을 하겠습니다.

 

numbers 의 배열을 순차로 돌면서 비교를 하게 됩니다.

첫번째로 back : 30 , front : 3 을 비교하게됩니다. 여기서 else 문의 compareTo 를 수행하게 되며 값은 아래와 같이 3 이라는 양수값이 나오게 됩니다. ("330" , "303" 을 비교하게되는데 첫번째 자리인 3끼리는 같기때문에 다음 자리 수인 3 과 0 을 비교해서 3 이라는 양수 값이 나오면 바로 return 하고 종료해서 3이 나옵니다.) 

 

여기서 양수값이 나오면 오름차순으로 두 수를 정렬시키고 음수값이 나오면 내림차순으로 두 수를 정렬시킵니다.

 

그럼 다음 비교를 보겠습니다.

 

처음에 3, 30 을 비교했으므로 다음엔 30 ,34 를 비교하게 됩니다.

30 과 34 를 compareTo 를 함으로써 -4 라는 값이 나오게 됩니다.

그렇다면 34 , 30 으로 내림차순 정렬이 될 것입니다.

 

마지막으로 다음 비교를 보겠습니다.

 

 

 

처음에 3, 30 은 비교해서 정렬이 되있었는데 3, 34 ,30 이 됬으므로 34 와 3 도 비교를 해서 정의를 해야 됩니다.

"334" , "343" 을 비교해서 두번째 자리 수에서 -1 값이 리턴되면서 34, 3 으로 내림차순 되게 됩니다.

결과론적으로 34, 3, 30  이렇게 정렬이 되게 됩니다.

 

 

해당 동작 방식으로 결과를 얻게 되면

최종적으로 정렬이 되서 나오게 됩니다.

Comparator 를 사용해서 조건에 맞게 정렬을 시킬 수 있습니다.