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

원사이트 : https://programmers.co.kr/learn/courses/30/lessons/42746#

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

1.문제설명

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

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

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

 

2.제한사항

• numbers의 길이는 1 이상 100,000 이하입니다.

• numbers의 원소는 0 이상 1,000 이하입니다.

• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

 

3.입출력 예

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

4.풀이(JAVA)

import java.util.*;

class Solution {
    public String solution(int[] numbers) {
        String answer = new String();
        /** 1 **/
        String str_numbers[] = new String[numbers.length];

        /** 2 **/
        for(int i=0; i<str_numbers.length; i++) {
            str_numbers[i] = String.valueOf(numbers[i]);
        }

        /** 3 **/
        Arrays.sort(str_numbers, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return (o2+o1).compareTo(o1+o2);
            }
        });

        /** 4 **/
        if(str_numbers[0].startsWith("0")) { 
            answer += "0";
        } else {
            for(int j=0; j<str_numbers.length; j++) {
                answer += str_numbers[j];
            }
        }

        return answer;
    }
}

5.분석 및 개선점

(분석)

1. 숫자 배열을 문자 배열로 변환.

2. 자바의 comparator 클래스의 compare를 오버라이드해 내림차순 구현.

3. 정렬된 배열로 문자열을 만들어 결과 반환.

 

(개선점)

1. 오버라이드된 compare함수는 Timsort라는 방식의 알고리즘을 따른다.

해당 알고리즘을 내부적으로 다른 방식으로 구현해보거나, 다른 알고리즘 방식을 사용하도록 

커스터마이징 해보는 것도 좋은 방식일 거 같다.

참고주소 : https://stackoverflow.com/questions/30638617/what-sorting-algorithm-used-while-overriding-compare-method-of-comparator-interf

What sorting algorithm used while overriding compare method of comparator interface?

 

Timsort : https://en.wikipedia.org/wiki/Timsort

Timsort - Wikipedia

병합정렬 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog