[프로그래머스/Java] 42746 가장 큰 수

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42746

프로그래머스

고찰 과정

나열할 수 있는 경우의 수를 다 파헤치기에는 numbers의 길이가 10만이기에 모든 경우의 수를 따지면서 큰 수를 추출하기에는 어려움이 있습니다. 게다가 제일 큰 수도 1000이 10만개 붙여진 수이기 때문에 매우 큰 수부터 생각하려고 해도 메모리 공간이 턱없이 부족합니다.

 

그래서 생각해본 또다른 방법은 numbers를 매우 큰 숫자가 나올 수 있도록 정렬하는 방법입니다. 방법은 다음과 같습니다.

1. 두 숫자를 비교할 때 두 숫자를 서로 붙여서 크기 비교를 한다.
2. 크기가 큰 숫자의 방향에 맞게 정렬을 한다.

저는 이들을 원활하게 정렬하기 위해서 Java의 Arrays.sort 내장함수를 사용하였고, Comparator 객체를 활용하여 정렬 기준을 정해주었습니다. 참고로 자바에 내장되어 있는 Arrays.sort() 함수는 Timsort 정렬 방식을 사용하기에 최악의 경우 O(nlogn)의 시간 복잡도를 가져 시간 안에 코드를 실행할 수가 있습니다.

 

---

코드

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

class Solution {
    public String solution(int[] numbers) {
        String[] sNumbers = Arrays.stream(numbers)
            .mapToObj(String::valueOf)
            .toArray(String[]::new);
        
        Arrays.sort(sNumbers, new Comparator<String>() {
            
            @Override
            public int compare(String o1, String o2) {
                return (o2 + o1).compareTo(o1 + o2);
            }
        });
        
        if (sNumbers[0].equals("0")) {
            return "0";
        }
        
        return Arrays.stream(sNumbers)
            .map(String::valueOf)
            .collect(Collectors.joining());
    }
}