프로그래머스 - 가장 큰 수 (커스텀 정렬, 문자열)

https://school.programmers.co.kr/learn/courses/30/lessons/42746?language=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"

---

접근

단순 정렬로 접근하려고 했지만, 바로 걸림돌로 느껴진 부분은 3 과 34 비교와 5 와 53 비교였다. 단순히 자바의 정렬 함수를 사용하기에는 자릿수가 다른 두 문자열을 어떻게 비교시키냐가 감이 안잡혔다.
그렇다고 모든 경우의 수를 비교하자니, 최대 1000개 원소의 순열은 1000!이므로 불가능하다. 여기서부터 꼬인 것 같다. 경우의 수를 비교하는 것은 불가능하다는 생각 때문에 커스텀 정렬의 기준을 마련하기 위한 패턴 찾기에만 빠져서 문제를 풀지 못했다.

---

해답

해답은 간단하지만 떠올리기 힘든 방식이였다. 결국 각 숫자들을 차례로 이어 붙인 후 더 큰 숫자를 만들면 되므로, 어떤 숫자가 앞에 올 때 사전적으로 더 큰지를 비교하면 된다.
단순히 비교가 어려운 (3 VS 34 / 5 VS 53 / a VS b) 의 경우, ab VS ba 중에 사전적으로 더 큰지를 비교하면 된다.
(ex. 334 < 343, 553 > ``535)

---

소스코드

public String solution(int[] numbers) {  
    String answer = "";  
    String[] strings = new String[numbers.length];  
    for (int i = 0; i < numbers.length; i++) {  
        strings[i] = String.valueOf(numbers[i]);  
    }  

    Arrays.sort(strings, (s1, s2) -> (s2 + s1).compareTo(s1 + s2));  

    if (strings[0].startsWith("0")) return "0";  
    for (String s : strings) {  
        answer += s;  
    }  
    return answer;  
}