코딩테스트 고득점 kit / 정렬 / 가장 큰 수 / 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

---

나의 풀이

import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public String solution(int[] numbers) {
        String answer = "";
        
        String[] stringNumbers = new String[numbers.length];
        for(int i=0; i<numbers.length; i++){
            stringNumbers[i] = String.valueOf(numbers[i]);
        }
        
        Arrays.sort(stringNumbers, new Comparator<String>(){
            @Override
            public int compare(String s1, String s2){
                return (s2+s1).compareTo(s1+s2);
            }
        });
        
        for(int i=0; i<stringNumbers.length; i++){
            answer += stringNumbers[i];
        }
        
        if(answer.charAt(0) == '0') answer = "0";
        
        return answer;
    }
}

---

풀이 분석

이 문제는 일반적으로 풀면 시간이 굉장히 오래걸린다. 처음엔 10으로 나눠서 digit단위로 만든다음 비교하려고 했으나 굉장히 비효율적이었기 때문에 다음과 같이 코드를 수정했다.

 

핵심은 문자열 더하기 이다. compareTo메소드를 알고있는지 여부가 이 문제를 풀 수 있는지를 결정한다. compareTo는 문자열 비교시 각 문자열에서 가장 낮은 아스키코드의 차이값을 리턴한다. 따라서 앞의 문자열의 뒤의 문자열보다 아스키코드가 더 낮으면 작은 수(음수 리턴)이고 반대면 큰 수(양수 리턴) 이다. 따라서 compareTo에 의해 compare메소드가 돌아가는 것이다.

 

compare 함수 사용시 s2+s1이 앞에 나오는 이유는 더 큰 숫자를 앞으로 보내기 위해서 이다. Comparator가 돌면서 계속해서 큰 숫자가 앞에 있으면 바꿔주기 때문이다. (좌측값이 크면 1리턴(바꿈), 리턴값이 -1이나 0이면 자리그대로) 

 

또한, 마지막에 "0000" 은 0으로 출력해줘야 테스트케이스가 전부 통과가 된다.

 

compareTo에 대한 자세한 내용은 다음 블로그에서 친절히 다루고 있다. 참고하면 좋을 것 같다.

[JAVA] 자바_compareTo ( 값 [문자열/숫자] 비교 )

---

히스토리

chucoding/algorithm