[정렬] 가장 큰 수

문제 파악하기

https://school.programmers.co.kr/learn/courses/30/lessons/42746?language=java

위 문제는 주어진 리스트의 숫자들을 합쳤을 때 가장 큰 수가 되도록 구하는 문제이다. 그리고 숫자 형태의 문자열로 출력해야 한다.

문제 해결하기

정렬을 할 때 조금 특이하게 커스텀 정렬을 수행해야 한다. 두 개의 문자열을 합쳤을 때, 어느 것이 앞에 있냐에 따라서 결정되야 한다. 코드는 다음과 같다.

import java.util.Arrays;
import java.util.Comparator;
import java.util.stream.Collectors;

class Solution {

    public String solution(int[] numbers) {
    	// 정렬후 합치기
        String num = Arrays.stream(numbers)
            .mapToObj(String::valueOf)
            .sorted((s1, s2) -> -(s1 + s2).compareTo(s2 + s1))
            .collect(Collectors.joining(""));
        
        // 문제에서 요구하는 숫자 형태로 만들기
        int startIndex = 0;
        for (int i = 0; i < num.length(); ++i) {
            if (num.charAt(i) != '0') {
                break;
            }
            startIndex++;
        }
        System.out.println(startIndex);
        return startIndex == num.length() ? "0" : num.substring(startIndex);
    }
}

아래의 요구하는 숫자 형태 만들기는 replaceFirst와 regex을 활용해서 다음과 같이 작성해도 된다.

String replaced = num.replaceFirst("^0+", "");
return replaced == "" ? "0" : replaced;

파이썬의 경우
functools의 cmp_to_key를 활용해서 문제를 풀 수 있다.

from functools import cmp_to_key


def solution(numbers):
    def compare(s1, s2):
        if (s1 + s2) < (s2 + s1):
            return -1
        if (s1 + s2) == (s2 + s1):
            return 0
        return 1
    num = "".join(sorted(map(str, numbers), key=cmp_to_key(compare), reverse=True))
    striped = num.lstrip("0")
    return "0" if striped == "" else striped