프로그래머스: 가장 큰 수 만들기

 

0 또는 양의 정수가 담긴 배열이 주어졌을 때, 이 숫자들을 조합하여 만들 수 있는 가장 큰 수를 반환하는 문제입니다.

예를 들어

입력: [6, 10, 2] 출력: "6210"

입력: [3, 30, 34, 5, 9] 출력: "9534330"

단, 결과가 너무 클 수 있으므로 정수형이 아닌 문자열로 반환해야 합니다.

 

해결 과정

1. 숫자를 문자열로 변환: Arrays.stream(numbers).mapToObj(String::valueOf).toArray(String[]::new);
2. 커스텀 정렬 적용: 두 숫자를 번갈아 붙여보고 (a + b vs b + a) 더 큰 순서대로 정렬합니다.
3. 예외 처리: 배열의 첫 번째 요소가 "0"이면 "0"을 반환합니다.
4. 정렬된 숫자를 하나의 문자열로 합쳐 결과 반환.

 

코드 구현

import java.util.*;

class Solution {
    public String solution(int[] numbers) {
        
        String[] strNumbers = Arrays.stream(numbers)
                                    .mapToObj(String::valueOf)
                                    .toArray(String[]::new);
        
        Arrays.sort(strNumbers, (a, b) -> (b + a).compareTo(a + b));
        
        if (strNumbers[0].equals("0")) {
            return "0";
        }
        
        return String.join("", strNumbers);
    }
}

 

코드 설명

1. 문자열 변환: 숫자 배열을 문자열 배열로 변환합니다.
2. 정렬 로직: 두 숫자를 앞뒤로 붙여 비교한 후, 더 큰 값을 앞에 오도록 정렬합니다.
3. 예외 처리: "0"만 존재하는 경우 "0"을 반환합니다.
4. 결과 반환: 정렬된 숫자를 문자열로 합칩니다.

 

시간 복잡도

• Arrays.sort()의 시간 복잡도는 O(N log N) 이므로, 100,000개의 숫자까지도 충분히 빠르게 동작할 수 있습니다.