[프로그래머스][JAVA]Lv. 2 - 가장 큰 수

 

https://school.programmers.co.kr/learn/courses/30/lessons/42746

프로그래머스

주어진 정수를 이용하여 가장 큰 수를 만드는 문제.

여러 방법을 써봤지만 O(n^2) 이상의 시간복잡도를 가지면 1~6번 테스트 케이스를 통과하지 못했다.

자바의 정렬은 듀얼피봇 퀵정렬(Dual-Pivot Quicksort) 또는 팀소트(Timsort) 알고리즘이 쓰인다고 한다.

둘의 시간 복잡도는 O(nlog n)에 가깝기 때문에 Compatator로 조건을 걸어서 정렬을 사용하였다.

Integer[] arr = new Integer[numbers.length];
for (int i = 0; i < arr.length; i++) {
    arr[i] = numbers[i];
}
Arrays.sort(arr, new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        String num1 = String.valueOf(o1) + String.valueOf(o2);
        String num2 = String.valueOf(o2) + String.valueOf(o1);
        return Double.compare(Double.parseDouble(num1), Double.parseDouble(num2));
    }
});

Comparator를 쉽게 사용하기 위해서 Integer[] arr에 numbers의 내용을 옮겼다. 

그리고 o1o2와 o2o1을 비교하여 o1o2가 더 크다면 서로의 위치를 바꾸게 하였다.

이렇게 숫자를 정리하고 나서

for (int i = arr.length - 1; i >= 0; i--) {
    answer.append(arr[i]);
}

더 큰수를 만들 수 있는 수가 뒤쪽으로 가도록 만들었기 때문에

뒤쪽에서 부터 answer에 추가해주었다.

String ans = answer.toString();
if (ans.charAt(0) == '0') return "0";

그리고 주어진 수가 0, 0, 0 같은 수일 수 있기 때문에, 첫 숫자가 0일 경우 0을 return 하도록 하였다.

import java.util.Arrays;
import java.util.Comparator;
class Solution {
    public String solution(int[] numbers) throws Exception {
        StringBuilder answer = new StringBuilder();

        Integer[] arr = new Integer[numbers.length];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = numbers[i];
        }
        Arrays.sort(arr, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                String num1 = String.valueOf(o1) + String.valueOf(o2);
                String num2 = String.valueOf(o2) + String.valueOf(o1);
                return Double.compare(Double.parseDouble(num1), Double.parseDouble(num2));
            }
        });
        
        for (int i = arr.length - 1; i >= 0; i--) {
            answer.append(arr[i]);
        }

        String ans = answer.toString();
        if (ans.charAt(0) == '0') return "0";

        return answer.toString();
    }
}