[JAVA]가장 큰 수(Programmers)

문제

문제

 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"

풀이

 문자형으로 정렬을 해야되겠다는 느낌이 문제를 읽자마자 들었다. 따라서 String배열을 선언해 값을 할당하고, 정렬을 해주었더니 대체적으로는 정렬이 되었으나 입출력 예#2와 같은 입력의 경우 3과 30이 제대로 정렬되지 않았다.

 고민을 계속하다가, 문자열의 길이가 다른 경우? 그러면 앞에서부터 하나하나 비교를 하다가 달라지는 부분에서 비교를 한다? 생각이 많아졌다.

 정현이형에게 어떻게 풀었냐고 물어봤더니, numbers의 원소가 1,000이하 즉, 길어봐야 네 자리를 넘지 않기에 수를 네자리로 만들어 비교를 진행하여 정렬을 했다고 한다.

 Comparator를 만들어 위와 같이 구현했더니 단 하나의 케이스만 빼고 정답처리가 되었다. 단 하나의 케이스는 0이 연속으로 들어오는 경우였다.

 다른 풀이를 구경하던 중, 단순히 compare의 e1과 e2를 비교할때, e1+e2와 e2+e1을 비교하는 방법이 있었다. 참신했다.

 아... 머리가 왜 이렇게 안 돌아갈까.

import java.util.*;
class Solution {
    public String solution(int[] numbers) {
        String[] str = new String[numbers.length];
        for(int i = 0; i < numbers.length; i++)
            str[i] = Integer.toString(numbers[i]);
        Arrays.sort(str, new Comparator<String>(){
            @Override
            public int compare(String e1, String e2){
                return (e2+e1).compareTo(e1+e2);
            }
        });
        String answer = "";
        if(str[0].matches("0"))
            return "0";
        else
            for(String s : str)
                answer += s;
        return answer;
    }
}