[프로그래머스 고득점 kit]정렬 Level2 가장 큰 수

문제 설명

 

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

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

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

 

제한 사항

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

입출력 예

numbers

return

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

 

문제 접근

 처음에는 단순히 배열의 원소를 모두 문자열로 타입 캐스팅을 수행하고 사전식으로 오름차순 배열한 후 모두 연결하면 해결될 수 있을 것 같았다. 하지만 ['12', '121'] 의 경우 사전식 오름차순 정렬 후 연결하면 '12112'이 되며 이수는 '12121' 보다 작은 수가 된다.

 

이를 해결할 수 있는 방안으로 두 가지가 떠올랐다.

 

첫 번째, 순열 알고리즘을 통해 모든 가능한 수의 조합을 구하고 이중 가장 큰 수를 선택한다.

이 해결 방안은 충분히 가능한 방안이지만 시간 복잡도가 O(n^2)이다. 배열의 최대 길이가 100000 = 10 * 10^4 총 시간 복잡도는 10 * 10^8 약 10억번 연산이 수행되기 때문에 배제하였다.

 

두 번째, 두 수를 앞뒤, 뒤앞으로 조합한 수를 비교하여 오름차순 정렬한다.

가장 처음 생각했던 정렬 방식은 단순히 각 수를 비교하여 오름차순 정렬하기 때문에 ['12', '121']와 같은 반례가 존재한다. 그렇다면 앞뒤, 뒤앞(12121, 12112)한 형태 자체를 비교한다면 위와 같은 반례는 해결 될 것이다.

 

두 번째 해결책을 적용한 결과 마지막 테스트 케이스를 통과하지 못하였다. 다시 문제를 천천히 읽기 시작하였다.

 

배열의 원소는 0이상 1000이하, 배열의 크기는 1 이상 100,000이하이다. 여기서 간과한 점, 당연히 0은 가장 작은 양의 정수이기 때문에 절대로 맨 앞에 존재할 수 없다는 것. 하지만 모든 배열의 원소가 0이라면 0은 수 조합의 가장 앞에 존재할 수 있다.

 

[0, 0, 0, 0]은 어떤 수로 표현 되어야할까?

 

'0000'이 아닌 '0'으로 표현되어야할 것이다. 

 

생성된 문자열의 맨 앞 Character가 0인 경우는 모든 원소가 0인 경우밖에 존재하지 않기 때문에, 이 경우 '0'을 반환하는 처리를 추가한다.

 

소스 코드

import java.util.*;
class Solution {
    public String solution(int[] numbers) {
        String[] strNums = new String[numbers.length];
        
        for(int i=0;i<numbers.length;i++){
            strNums[i] = String.valueOf(numbers[i]);
        }
        
        Arrays.sort(strNums, new Comparator<>(){
            public int compare(String s1, String s2){
                return (s2 + s1).compareTo(s1 + s2);
            }
        });
        
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<strNums.length;i++){
            sb.append(strNums[i]);
        }
        if(sb.charAt(0) == '0'){
            return "0";
        }
        return sb.toString();
    }
}