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

개요

• 0 또는 양의 정수가 담긴 배열 numbers가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내라.

 

<조건>

• 알 수 없음

 

<입력>

• int[] numbers: 0 또는 자연수가 들어있는 배열 (1 ~ 100,000, 10^5)
  • 각 원소의 값: 0 ~ 1,000(10^3)

 

<반환>

• 정답은 String으로 리턴하라.

 

 

문제 풀이

처음에는 정수 각 자리수를 문자로 변경한 뒤에,

문자 배열에 넣고 정렬하는 식으로 문제에 접근했는데, 

 

문제에서 요구하는 사항은 주어진 정수를 분해하는 것은 아니었으므로 잘못된 접근이었다.

 

 

결국 문자열로 바꾼 뒤 정렬하는 것이라고 생각했는데

-> 사전 순으로 나열하면 왠지 될 것 같아서?

 

 

단순히 문자열 배열을 내림차순으로 정렬할 경우

문자열끼리 직접 비교하게 되므로

 

두 번째 예제에서

9
5
34
30
3

으로 3이 30보다 늦게 나오게 되어 문제가 생긴다.

 

 

고민해본결과

두 문자열을 합쳐보는 건 어떨까? 하고 생각이 들었다.

 

예를 들어 a와 b를 비교할 때

a+b와 b+a를 비교하는 식으로 하면 해결될 거 같았다.

 

위에서 나온 문제도

"30" + "3" = 303

"3" + "30" = 330

으로  해결된다.

 

 

 

그래서 핵심 코드는 다음과 같다.

Arrays.sort(str, new Comparator<String>(){
    @Override
    public int compare(String s1, String s2){
        return (s2+s1).compareTo(s1+s2);
    }
});

Arrays.sort()의 Comparator를 직접 만들어서

String의 .compareTo()메서드로 비교해주는 것이 핵심이었다.

 

 

주의할 점이 하나 존재하는데

numbers의 수는 0도 주어질 수 있으므로, 모든 값이 0이면 "000..."으로 리턴될 것이다.

 

이걸 방지하기 위해

answer 문자열의 첫 번째 인덱스를 검사하여 0이 나오면 "0"만 리턴하도록 코드를 짰다.

String answer = sb.toString();
if(answer.charAt(0) == '0') return "0";
return answer;

 

 

 

 

전체 코드

import java.util.*;

class Solution {
    public String solution(int[] numbers) {
        
        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);
            }
        });
        
        StringBuilder sb = new StringBuilder();
        for(String s: str){
            sb.append(s);
        }
        
        String answer = sb.toString();
        if(answer.charAt(0) == '0') return "0";
        return answer;
    }
}

 

 

 

 

배운 점

Arrays.sort()를 사용할 때

Comparator를 인자로 주어 직접 정렬 기준을 만드는 방법에 대해 배울 수 있었던 문제였다.