[프로그래머스] 가장 큰 수 (Level 2, Java) - 문자열 조합 정렬 기준 설계

문제 정보

• 문제 링크: 프로그래머스 - 가장 큰 수 (42746)
• 난이도: Level 2

핵심 조건 및 제한 사항

• 0 또는 양의 정수가 담긴 배열 numbers의 원소들을 이어 붙여 만들 수 있는 가장 큰 수를 문자열로 반환합니다.
• numbers의 길이: 1 이상 100,000 이하
• numbers의 원소: 0 이상 1,000 이하
• 예시: [3, 30, 34, 5, 9] → "9534330"

---

접근 아이디어

1. 단순 내림차순 문자열 정렬의 함정

단순히 숫자를 문자열로 바꾼 뒤 내림차순(s2.compareTo(s1))으로 정렬하면 어떻게 될까요?

• "30"과 "3"을 사전순으로 비교하면 "30" > "3"이 되어 "30"이 앞에 옵니다.
• 하지만 실제로 이어 붙이면 "303"보다 "330"이 더 큽니다!

2. 핵심 비교 기준: (s2 + s1).compareTo(s1 + s2)

두 숫자 문자열 s1, s2의 우선순위를 결정하는 가장 확실한 방법은 실제로 두 가지 순서로 이어 붙인 결과를 비교하는 것입니다.

• s1 + s2 vs s2 + s1
• 두 문자열은 길이가 동일하므로(len(s1) + len(s2)), String.compareTo를 사용한 사전순 비교 결과가 곧 정수 크기 비교 결과와 완전히 일치합니다.
• 내림차순(큰 조합이 앞으로 오도록)으로 정렬하려면 (s2 + s1).compareTo(s1 + s2)를 사용합니다.

비교 쌍 (s1, s2)	s1 + s2	s2 + s1	우선 배치
"3", "30"	"330"	"303"	"3"
"3", "34"	"334"	"343"	"34"
"30", "34"	"3034"	"3430"	"34"

3. 엣지 케이스: 모든 원소가 0인 경우

만약 numbers = [0, 0, 0]이라면 정렬 후 이어 붙인 문자열은 "000"이 됩니다. 하지만 숫자로 표현할 수 있는 가장 큰 수는 "0"이므로, 정렬 결과의 첫 번째 원소가 "0"이라면 전체가 0으로만 이루어진 배열임을 이용해 즉시 "0"을 반환해야 합니다.

---

Java 풀이 코드

import java.util.Arrays;
import java.util.List;

class Solution {
    public String solution(int[] numbers) {
        List<String> result = Arrays.stream(numbers)
                .mapToObj(String::valueOf)
                // 두 수를 이어 붙였을 때 더 큰 쪽이 앞에 오도록 내림차순 정렬
                .sorted((s1, s2) -> (s2 + s1).compareTo(s1 + s2))
                .toList();

        // 가장 큰 숫자가 "0"이면 모든 원소가 0이므로 "0" 반환
        return result.get(0).equals("0") ? "0" : String.join("", result);
    }
}

참고 (Java 버전 호환성): Stream.toList()는 Java 16 이상에서 지원됩니다. Java 8/11 환경에서는 .collect(Collectors.toList())를 사용하거나 String[] 배열로 Arrays.sort()를 호출하면 됩니다.

---

채점 결과

---

복잡도 분석

• 시간 복잡도: O(N log N) — N개의 짧은 문자열(최대 4자리)을 정렬하며, 비교당 문자열 길이 L <= 8이므로 실질적으로 O(N log N) 내에 동작합니다.
• 공간 복잡도: O(N) — 문자열 리스트 및 최종 결과 문자열 생성 비용