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

문제 설명

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

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

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

제한 사항

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

입출력 예

numbers	return
[6, 10, 2]	"6210"
[3, 30, 34, 5, 9]	"9534330"

 

---

풀이 접근

 

1. 숫자를 문자열로 변환하여 비교

2. 두 수를 이어 붙였을 때 더 큰 수가 되는 순서로 정렬

3. 정렬된 문자열들을 이어 붙여 결과를 반환

 

코드

import java.util.Arrays;
class Solution {
    public String solution(int[] numbers) {
        // 숫자를 문자열로 변환
        String[] strNums = new String[numbers.length];
        for(int i = 0; i < numbers.length; i++){
            strNums[i] = String.valueOf(numbers[i]);
        }
        
        // 두 수를 이어붙였을 때 더 큰 수가 되는 순서로 정렬
        Arrays.sort(strNums, (a, b) -> (b + a).compareTo(a + b));
        
        // 정렬된 문자열 이어붙이기
        String answer = String.join("", strNums);
        return answer;
    }
}

 

compareTo를 이용한 정렬 이해하기

이 문제에서 가장 헷갈렸던 부분은 compareTo를 이용한 정렬이다.

compareTo는 다음과 같이 동작한다

1. compareTo의 기본 동작
   • 음수 반환: 왼쪽 문자열이 오른쪽보다 사전순으로 앞에 위치
   • 양수 반환: 왼쪽 문자열이 오른쪽보다 사전순으로 뒤에 위치
   • 0 반환: 두 문자열이 같음
2. Arrays.sort에서의 동작
   • 음수가 반환되면: 현재 순서 유지
   • 양수가 반환되면: 순서 변경
3. 예시로 이해하기
   ```
   // 예: a="6", b="10" 인 경우
   (b + a).compareTo(a + b)  // "106".compareTo("610")
   ```
   
   • \"106"이 "610"보다 사전순으로 앞에 있으므로 음수 반환
   • 음수가 반환되었으므로 현재 순서(6, 10) 유지
   • 결과적으로 더 큰 수가 되는 "610"을 만드는 순서가 됨