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

▪︎ 문제

---

프로그래머스 가장 큰 수

▪︎ 알고리즘 설계

---

1. int → String 변환
   • 비교 시 문자열 결합(a+b, b+a) 결과를 기준으로 하기 위해 숫자를 문자열로 변환한다.
2. 정렬 기준 설정
   • 단순 내림차순 정렬이 아니라, 두 문자열 a, b를 비교할 때 (b+a).compareTo(a+b) 로 비교
   • 예: "40" vs "403" → "40403" vs "40340" → "40"이 먼저 와야 한다.
3. 전부 0 처리
   • 배열이 [0, 0, 0] 같은 경우 "000"이 아니라 "0" 반환
4. 문자열 이어 붙이기
   • StringBuilder로 성능 최적화하며 결과 문자열 생성

▪︎ 코드

---

import java.util.*;

class Solution {
    public String solution(int[] numbers) {
        String[] intToString = new String[numbers.length];
        
        // 1. int → String 변환
        for (int i = 0; i < numbers.length; i++) {
            intToString[i] = String.valueOf(numbers[i]);
        }
        
        // 2. 정렬
        Arrays.sort(intToString, (a, b) -> (b + a).compareTo(a + b));
        
         // 3. 가장 큰 수가 0이면 (즉, 전부 0이면) 0 반환
        if (intToString[0].equals("0")) return "0";
        
        // 4. 이어 붙이기
        StringBuilder sb = new StringBuilder();
        for (String s : intToString) {
            sb.append(s);
        }
        
        return sb.toString();
    }
}

• (a, b) -> (b + a).compareTo(a + b)
  • a, b: 정렬한 대상 배열의 두 원소
  • (a + b): 문자열 a 뒤에 문자열 b를 붙인 결과
  • (b + a): 문자열 b 뒤에 문자열 a를 붙인 결과
  • .compareTo(…): 두 문자열을 사전순으로 비교
    • compareTo > 0 → 왼쪽이 더 크다 → 자리를 바꿈
    • 음수 → 왼쪽이 더 작다 → 그대로 둠

▪︎ 시간복잡도

---

• 정렬: Arrays.sort() → O(N log N)
  • 비교 연산에서 문자열 덧셈이 길이 최대 4자리 정도이므로 O(1)로 취급 가능
• 문자열 합치기: O(N)
• 총합: O(N log N)

▪︎ 틀린 이유

---

import java.util.*;

class Solution {
    public String solution(int[] numbers) {
        
        String[] intToString = new String[numbers.length];
        
        for(int i = 0; i < numbers.length; i++) {
            intToString[i] = Integer.toString(numbers[i]);
        }
        
        Arrays.sort(intToString, Collections.reverseOrder());
        
        String result = intToString[0];
        
        for(int i = 1; i < intToString.length; i++) {
            result += intToString[i];
        }
        
        return result;
    }
}

• 단순 내림차순 정렬은 이어붙였을 때 가장 큰 수를 보장하지 않음
  • 예: [40, 403] → 내림차순: "403", "40" → "40340" (X) 올바른: "40", "403" → "40403" (O)
  • 따라서 두 수를 이어붙였을 때 더 큰 쪽이 먼저 오도록 비교해야 함

▪︎ 느낀점 / 기억할 정보

---

• 문제 핵심은 단순 숫자 비교가 아니라, “붙였을 때 더 큰 문자열”을 기준으로 정렬하는 것
• 모든 원소가 0일 때는 “000”이 아닌 “0” 반환
• StringBuilder는 문자열을 반복 연결할 때 성능 이점이 있음 (+ 연산은 매번 새로운 객체 생성)
• 정렬 비교 로직 (b+a).compareTo(a+b) 는 문자열 비교 문제에서 자주 쓰이는 패턴이므로 기억