[Algorithm/Programmers] 자바 - 가장 큰 수

문제	플랫폼	난이도	유형	풀이 링크	문제 링크
가장 큰 수	Programmers	Level 2	Sort	풀이	문제

풀이

0 또는 앙의 정수가 주어지고,
이를 이어 붙여 가장 큰 수를 만들어야 합니다.

주어진 수의 순서를 어떻게 재배치 할 지 고민해봐야 할 것 같습니다.
특별한 수학적 아이디어가 없다면, 전체 경우의 수 중 가장 큰 수를 골라도 될 것입니다.
하지만, 내림차순 정렬을 통해 쉽게 가장 큰 수를 구할 수 있습니다.

다만, Java에서 내림차순 정렬을 할 때, Comparator 객체를 직접 구현해야 합니다.
Collections.reverseOrder()가 있지만, 결국 이도 Comparator 객체이고, primitive type사용 시 wrapper class로 변경해서 해야 하므로,
그냥 알고리즘 풀 때는 간단하게 구현해서 하는 게 편합니다.

public String solution(int[] numbers) {
    // 문자열을 return할 배열 생성
    String[] str = new String[numbers.length];

    int len = str.length;
    // 1. int to String
    for (int i = 0; i < len; i++) {
        str[i] = String.valueOf(numbers[i]);
    }

    // 2. Desc Sort
    Arrays.sort(str, new Comparator<String>() {
        @Override
        public int compare(String o1, String o2) {
            return (o2+o1).compareTo(o1+o2);
        }
    });

    // 3. Get Answer
    String ans = "";
    if (str[0].equals("0")) { // 내림차순 정렬을 했으므로, 0번째 인덱스가 "0"일 시, 모두 0
        ans += "0";
    } else {
        for (int i = 0; i < len; i++) {
            ans += str[i];
        }
    }

    return ans;
}

Java Comparator 구현

String Desc

Arrays.sort(str, new Comparator<String>() {
        @Override
        public int compare(String o1, String o2) {
            return (o2+o1).compareTo(o1+o2);
        }
    });

Arrays.sort(str, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));

String Asc

Arrays.sort(str, new Comparator<String>() {
        @Override
        public int compare(String o1, String o2) {
            return (o1+o2).compareTo(o1+o2);
        }
    });

Arrays.sort(str, (o1, o2) -> (o1 + o2.compareTo(o1 + o2));

a.compareTo(b)

• 앞에서부터 차례대로 비교하다가,
  다른 문자열이 나오면 "a-b" 순서로 해당 문자의 아스키코드 값을 뺀 int 를 리턴합니다.

내림차순 : (o2+o1).compareTo(o1+o2);
오름차순 : (o1+o2).compareTo(o1+o2);

Stream, Lambda

String str = "ACBED"; 
String[] str = str.split(""); // to array

Stream.of(str).sorted().collect(Collectors.joining()); // ASC
Stream.of(str).sorted(Comparator.reverseOrder()).collect(Collectors.joining()); // DESC
Stream.of(str).sorted((o1,o2)->o1.compareTo(o2)).collect(Collectors.joining()); // ASC
Stream.of(stringArr).sorted((o1,o2)->o2.compareTo(o1)).collect(Collectors.joining()); // DESC

추가적으로 자바에서 정렬을 위한 인터페이스로,
Comparable과 Comparator 두 가지가 있습니다.
Comparable 인터페이스는 보통 객체의 고정된 정렬을 위해 사용하고,
Comparator 인터페이스는 기본 정렬과 다르게 정렬할 때 사용합니다.