[프로그래머스, 자바] 가장 큰 수 - 정렬

프로그래머스 2단계 가장 큰 수 문제

 url : https://programmers.co.kr/learn/courses/30/lessons/42746?language=java

문제설명

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

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

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

제한사항

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

입출력 예

numbers	return
[6, 10, 2]	6210

자바코드

            
import java.util.Arrays;
class Solution {
    public static String solution(int[] numbers) {
        String[] arr = new String[numbers.length];
        for (int i = 0; i < numbers.length; i++)
            arr[i] = String.valueOf(numbers[i]);

                Arrays.sort(arr, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));


        if(arr[0].equals("0")) return "0";
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < arr.length; i++)
            sb.append(arr[i]);

        return sb.toString();
    }
}

문제설명

처음에 문제를 접했을 때는 문자열로 변경해서 문자열 정렬을 하면 손 쉽게 풀 수 있을거라 생각했다. 하지만 그렇지 않았다. 예외가 있었다. 

[3, 31, 34] 인 경우 문자열로 정렬했을 때, 34 31 3 으로 정렬이 된다. 그렇기 때문에 기본적인 문자열 정렬로는 해결이 되지 않았다.

계수정렬, 기수정렬 정말 많은 방식을 고민했다. 하지만 해답은 생각보다 간단했다.

결국은 정렬기준을 만들 수 밖에 없었고, Comparable 인터페이스를 구현할 수 밖에 없었다. 그리고 코드의 간결성을 위해 익명 구현 객체를 통해 구현했다.

결국은 3 과 31을 정렬하기 위해, 331 과 313을 비교해서 문자열로서 더 큰 문자열을 만드는 순으로 정렬했다. 

그리고 함수를 보면 if(arr[0].equals("0")) 일때, 0을 바로 리턴하는 조건문이 있다. 이 조건문은 입력값이 {0,0,0,0} 일 경우 0000으로 출력되지 않고 0으로 출력될 수 있게 한다.

문제를 풀고 다른 풀이법을 확인해봤는데, 대부분이 위와 같이 풀었다. 

최근에 공부해야할 내용이 많고, 개인적으로 진행하는 개발이 있어서, 간단한 알고리즘을 많이 풀었는데... 어제 카카오페이 알고리즘을 풀면서 더 열심히 해야겠다고 느꼈다.

이제는 다시... 알고리즘을 더 집중적으로 해봐야겠다!