[2단계] 가장 큰 수

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

프로그래머스

이문제를 DFS로 풀려다가 시간복잡도 때문에, 다시 정렬로 돌아왔다.

숫자들의 앞자리가 큰 수가 먼저오도록 내림차순을 해야한다.

 

비교 기준은 두 수를 앞+뒤, 뒤+앞으로 붙였을때로 잡는 것이 핵심이다.

 

Arrays.sort() 내부에서 Comparator의 compareTo()를 이용하는 방식을 이용했다.

(o2 + o1).compareTo(o1+o2)는 내림차순 정렬이고,

(o1 + o2).compareTo(o2+o1)은 오름차순 정렬

 

이문제는 큰수를 만들어야 하므로 내림차순 정렬을 해주어야 한다.

 

String은 문자가 추가되면 기존 객체를 재사용하는 것이 아니라 새 객체를 생성한다. 메모리 측면에서 굉장히 낭비가 되므로,

StringBuilder를 사용해주었다.

 

0,0,0,... 인경우도 생각해주어야한다.

정렬을 하고난 배열의 맨 처음 값이 0이면, 나머지값은 무조건 0일 수 밖에 없으므로

0일경우 바로 0을 리턴해주었다.

import java.util.Arrays;

class Solution {

    public String solution(int[] numbers) {

        String[] arr = new String[numbers.length];

        for (int i = 0; i < arr.length; i++) {
            arr[i] = String.valueOf(numbers[i]);
        }

        // 앞에서 뒤에것 빼기
        Arrays.sort(arr,(o1,o2) -> (o2 + o1).compareTo(o1 + o2));

        if("0".equals(arr[0])){
                    return "0";
        }

        StringBuilder answer = new StringBuilder();

        for (int i = 0; i < arr.length; i++) {
            answer.append(arr[i]);
        }

        return answer.toString();
    }

    public static void main(String[] args) {
        System.out.println(new Solution().solution(new int[]{6, 10, 2}));
    }
}