[프로그래머스 스쿨] 코딩테스트 연습 - 가장 큰 수

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 조건

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

입출력 예 설명

기본 코드

class Solution {
    public String solution(int[] numbers) {
        String answer = "";
        return answer;
    }
}

내가 구현한 코드

import java.util.*;
class Solution {
    public String solution(int[] numbers) {
        String answer = "";
        
        String str[] = new String[numbers.length];
        
        for(int i=0; i<numbers.length; i++) {
            str[i]=Integer.toString(numbers[i]);
        }
        Arrays.sort(str, new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                return (s2+s1).compareTo(s1+s2);
            }
        });
        if(str[0].equals("0")) return "0";
        
        for(int i=0; i <str.length; i++) {
            answer += str[i];
        }
        return answer;
    }
}

문제 해결

• 정수 배열을 문자열 배열로 변환
  • 숫자를 이어붙여 비교해야 하므로, 모든 정수를 문자열로 바꾼다.
• 정렬 기준 정의
  • 문자열 s1, s2가 있을 때 (s1+s2) 와 (s2+s1)을 비교한다.
  • 두 문자열을 이어붙였을 때 더 큰 값을 만드는 순서대로 정렬한다.
  • 예: "6"과 "10" → "610" vs "106" → "610"이 크므로 "6"이 "10"보다 앞에 와야 한다.
• 정렬 수행
  • Arrays.sort() 와 사용자 정의 Comparator를 이용한다.
  • 정렬된 결과는 가장 큰 수를 만들 수 있는 순서가 된다.
• 결과 문자열 생성
  • 정렬된 문자열 배열을 차례대로 이어붙여 최종 문자열을 만든다.
• 예외 처리
  • 정렬 후 첫 번째 값이 "0"이라면, 모든 원소가 0이라는 의미다.
  • 이 경우 "000..." 대신 "0"만 반환한다.

중요한 점

• 문자열 비교 기준
  • 단순한 숫자 크기 비교가 아니라 두 수를 붙였을 때의 크기로 비교해야 한다.
  • (s1+s2) vs (s2+s1) 비교가 문제 해결의 핵심이다.
• 성능 고려
  • numbers 길이가 최대 100,000까지 가능하므로 정렬은 O(N log N).
  • Comparator 내부에서 문자열 연산이 반복되므로 효율성 고려가 필요하다.
• 0 예외 처리
  • "0"이 가장 앞에 온다면 전체가 "0"이라는 의미 → "0" 하나만 반환.
• 문자열 연결 방식
  • answer += str[i] 보다는 StringBuilder 사용이 성능상 유리하다.
  • + 연산은 새로운 문자열 객체를 매번 생성하기 때문이다.