[프로그래머스] 가장 큰 수 풀이 (정렬)

문제 소개

오늘 풀었던 프로그래머스 - 가장 큰 수 문제를 정리합니다.

이 문제는 여러 정수를 이어 붙여서 만들 수 있는 가장 큰 수를 찾는 문제입니다.
단순히 숫자 크기 순으로 정렬하는 것이 아니라, 이어 붙였을 때 더 큰 숫자가 되는 순서를 기준으로 정렬해야 합니다.

문제 링크: 가장 큰 수 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 숫자를 문자열로 변환하여 배열에 저장합니다.
2. 두 문자열을 이어붙인 결과 (ab, ba)를 비교하여 더 큰 쪽을 우선하도록 정렬합니다.
3. 정렬이 끝난 문자열들을 차례로 이어붙여 최종 결과를 만듭니다.
4. 가장 앞자리가 0이면(예: [0, 0, 0]) 결과는 "0"을 반환합니다.

---

해결 과정 및 코드

핵심 아이디어

1. "a"+"b"와 "b"+"a"를 비교하여 더 큰 문자열이 앞에 오도록 정렬한다.
2. 모든 숫자를 문자열로 변환하고, 정렬 후 이어붙인다.

코드

시간 복잡도 : O(N log N)

import java.util.*;

class Solution {
    public String solution(int[] numbers) {
        StringBuilder sb = new StringBuilder();
		// int -> String 변환        
        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";
        for (String str : strNumbers) {
            sb.append(str);
        }
        return sb.toString();
    }
}