[정렬] 가장 큰 수 (JAVA)

# 문제 설명

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"

 

# 정답 코드

public static String solution(int[] numbers) {
        String[] list = new String[numbers.length];

        for (int i = 0; i < list.length; i++) {
            list[i] = Integer.toString(numbers[i]);
        }

        Comparator<String> cp = new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) { //o1 = 3, o2 = 30
                String order1 = o1 + o2; //330
                String order2 = o2 + o1; //303

                // 내림차순으로 정렬
                return order2.compareTo(order1); //330 > 303이므로 3이 30보다 앞으로 정렬됨
            }
        };

        Arrays.sort(list, cp);

        String answer = "0";

        //{0, 0, 0}일 때 0이 리턴되어야 함
        for (String l : list) {
            if (answer.equals("0") && l.equals("0")) {
                answer = "0";
            }
            else if (answer.equals("0")) {
                answer = l;
            }
            else {
                answer = answer + l;
            }
        }

        return answer;
    }

 

int 배열인 numbers를 String 배열인 list로 옮겨준다.

 

가장 큰 수를 만드려면 각 문자의 맨 앞 숫자가 큰 순서대로 정렬한다. (내림차순 정렬)

맨 앞 숫자가 같은 경우에는 두 수를 합쳤을 때 더 큰 경우대로 정렬한다.

 

예를 들어, 3과 30이 있을 때 맨 앞 숫자가 3으로 같다.

두 수를 합쳤을 때 나올 수 있는 경우는 330, 303이 있다.

330이 더 크므로 3, 30 순으로 정렬한다.

 

이 조건을 comparator를 이용하여 만들어주고, list를 정렬한다.

정렬된 순서대로 숫자를 합치면 가장 큰 수가 만들어진다.

 

이때 예를 들어 리스트가 {0, 0, 0}인 경우, 답은 000이 아닌 0이 되어야한다.

따라서 문자를 합칠 때 조건을 정해줘야 한다.