import java.util.*;
import java.util.stream.*;

class Solution {
    public String solution(int[] numbers) {
        // 정수 배열을 문자열 배열로 변환
        String result = Arrays.stream(numbers)
            .mapToObj(String::valueOf)  // 각 정수를 문자열로 변환
            .sorted((a, b) -> {  // 정렬 기준을 커스터마이징
                String ab = a + b;  // a를 먼저 이어붙인 경우
                String ba = b + a;  // b를 먼저 이어붙인 경우
                return ba.compareTo(ab);  // 큰 순서대로 정렬
            })
            .collect(Collectors.joining());  // 문자열로 이어붙임

        // 모든 숫자가 0인 경우 예외 처리
        return result.startsWith("0") ? "0" : result;
    }
}

 Approach

이 문제는 주어진 숫자 배열에서 가장 큰 수를 만들기 위해 각 숫자를 특정한 방식으로 정렬하고, 이를 조합하는 문제입니다. 핵심은 각 숫자를 문자열로 변환한 뒤, 그 조합에 따라 정렬 기준을 설정하는 것입니다. 단계별로 살펴보겠습니다.

1. 문제 분석

주어진 숫자 배열에서 가장 큰 수를 만들기 위해 각 숫자를 문자열로 변환한 후, 그 문자열을 비교하여 최적의 순서를 찾아야 합니다. 예를 들어, 숫자 a와 b가 있을 때, a + b와 b + a를 비교하여 더 큰 값이 나오도록 두 문자열을 정렬합니다. 이렇게 하면 최종적으로 이어붙인 숫자가 가장 큰 값을 가지게 됩니다.

2. 문자열 변환

먼저 주어진 숫자 배열을 문자열 배열로 변환해야 합니다. 이를 위해 모든 숫자를 문자열로 변환하는 과정이 필요합니다.

Solution.java

// 숫자를 문자열로 변환한 배열 생성
String[] strNumbers = new String[numbers.length];
for (int i = 0; i < numbers.length; i++) {
    strNumbers[i] = String.valueOf(numbers[i]);
}

숫자 배열을 순회하면서 각 숫자를 문자열로 변환해 새로운 배열에 저장합니다.

3. 정렬 기준 설정

이 문제의 핵심은 문자열 배열을 특정 기준에 따라 정렬하는 것입니다. 이 정렬 기준을 올바르게 설정하는 것이 문제 해결의 열쇠입니다. 여기서는 Comparator를 직접 구현하여 두 문자열을 비교하고, 이를 통해 정렬하였습니다.

Solution.java

// 두 문자열을 결합하여 비교한 후, 정렬 순서를 결정
Arrays.sort(strNumbers, (a, b) -> { 
    String ab = a + b;  // a를 앞에, b를 뒤에 결합
    String ba = b + a;  // b를 앞에, a를 뒤에 결합
    return ba.compareTo(ab);  // 더 큰 값을 만드는 순서로 정렬
});

Arrays.sort():
- 배열을 정렬할 때 사용하는 메서드입니다.
- 두 번째 인자로 Comparator를 받아 정렬 기준을 정의할 수 있습니다.
Comparator<T>:
- Java의 함수형 인터페이스로, 두 개의 객체를 비교하여 그들의 순서를 결정하는 데 사용됩니다.
- 이 인터페이스는 두 객체를 받아서 비교하고, 그 결과로 정수 값을 반환합니다.
- Comparator<T>의 핵심 메서드인 compare(T o1, T o2)는 다음과 같은 규칙에 따라 정수 값을 반환합니다:
  - 양수: 첫 번째 객체 o1이 두 번째 객체 o2보다 순서상 뒤에 있어야 함을 의미합니다. 즉, o2가 o1보다 앞에 오도록 정렬됩니다.
  - 음수: 첫 번째 객체 o1이 두 번째 객체 o2보다 순서상 앞에 있어야 함을 의미합니다. 즉, o1이 o2보다 앞에 오도록 정렬됩니다.
  - 0: 두 객체 o1과 o2가 순서상 동일하다는 것을 의미합니다. 이 경우, 두 객체의 위치는 바뀌지 않습니다.
  - 따라서, Comparator는 반환 값에 따라 배열이나 컬렉션 내 객체들의 순서를 정렬하는 기준을 제공하며, 이 기준에 따라 객체들이 정렬됩니다. 이 원리를 활용하여 객체의 정렬 기준을 자유롭게 커스터마이즈할 수 있습니다.
String.compareTo():
- 두 문자열을 사전순으로 비교하는 메서드입니다.
- A.compareTo(B)는 A가 B보다 크면 양수, 같으면 0, 작으면 음수를 반환합니다.
- 이를 통해 두 문자열을 이어붙였을 때 어느 쪽이 더 큰 숫자를 만드는지 판단합니다.
- 예를 들어, ba가 ab 보다 더 크다면 b가 a보다 앞에 오게 됩니다.

다음은 주어진 배열 [3, 30, 34, 5, 9]의 각 요소를 비교하고, 정렬되는 과정을 표현한 것입니다:

a	b	ab	ba	ab vs ba
"3"	"30"	"330"	"303"	"330" > "303"
"30"	"34"	"3034"	"3430"	"3034" < "3430"
"3"	"34"	"334"	"343"	"334" < "343"
"5"	"34"	"534"	"345"	"534" > "345"
"5"	"9"	"59"	"95"	"59" < "95"
"3"	"5"	"35"	"53"	"35" < "53"
"30"	"9"	"309"	"930"	"309" < "930"
"34"	"9"	"349"	"934"	"349" < "934"

이 과정을 통해 각 숫자의 비교 결과를 반영한 최종 정렬 순서는 [9, 5, 34, 3, 30]와 같이..

4. 문자열 결합

정렬된 문자열 배열을 하나의 문자열로 결합합니다. 여기서는 StringBuilder를 사용하였습니다:

Solution.java

// 배열의 모든 원소 하나의 문자열로 결합
StringBuilder result = new StringBuilder();
for (String str : strNumbers) {
    result.append(str);
}

5. 예외 처리

결과 문자열이 "0"으로 시작하는 경우, 이는 주어진 숫자 배열의 모든 원소가 0임을 의미합니다. 이러한 경우, 모든 원소를 이어 붙이면 "000..."과 같은 형태의 문자열이 생성될 수 있습니다. 따라서, 이 상황에서는 예외 처리를 통해 최종 결과를 "0"으로 반환해야 합니다.

Solution.java

// 배열의 모든 원소가 `0`인 경우 예외 처리
if (result.charAt(0) == '0') {
    return "0";
}

6. 최종 결과 반환

모든 단계를 거쳐 결합된 문자열을 반환합니다.

// StringBuilder의 내용을 문자열로 변환하여 반환
return result.toString();

Stream을 활용한 방법

위 과정을 하나로 합치면, Stream을 활용하여 보다 간결하게 처리할 수 있습니다. 이 접근 방식에서는 배열을 변환, 정렬, 결합하는 작업을 한 줄로 표현할 수 있습니다.

String result = Arrays.stream(numbers)
    .mapToObj(String::valueOf)
    .sorted((a, b) -> (b + a).compareTo(a + b))
    .collect(Collectors.joining());

return result.startsWith("0") ? "0" : result;

이 방법은 코드의 가독성을 높이며, 단계를 간결하게 표현할 수 있는 장점이 있습니다.

󰄉 Complexity

⏳ TC: O(n log n)
💾 SC: O(n)

이 알고리즘은 배열의 크기인 n에 대해 O(n log n)의 시간 복잡도를 가지며, 추가적인 문자열 배열을 생성하기 때문에 O(n)의 공간 복잡도를 가집니다. 이는 100,000개의 숫자에 대해서도 충분히 효율적입니다.

이 문제는 문자열 정렬을 활용한 그리디 접근법으로 해결할 수 있으며, 각 단계에서 주어진 조건을 꼼꼼히 구현하는 것이 중요합니다.

Algorithm
Sorting