[Algo Rhythm🕺💃] 프로그래머스 고득점 Kit 가장 큰 수

문제 설명

 

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

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

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

 

제한 사항

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

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

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

나는 어떻게 풀었나

 

import java.util.Arrays;

class Solution {
    public String solution(int[] numbers) {
        String answer = "";
        
        //initialize
        Integer[] numArr = new Integer[numbers.length];
        for(int i = 0; i < numbers.length; i++) {
            numArr[i] = numbers[i];
        }
        
        // sort
        Arrays.sort(numArr, (o1, o2) -> {
            String t1 = o1.toString();
            String t2 = o2.toString();
            
            return (t2 + t1).compareTo(t1 + t2);
        });
        
        //concatenating
        for(int i = 0; i < numArr.length; i++) {
            answer += numArr[i];
        }
        
        //exception
        if(answer.startsWith("0")) return "0";
        
        return answer;
    }
}

 

나는 왜 저렇게 풀었나

 

문제 설명에 나온 예제를 유심히 살펴본 결과 숫자들이 내림차순으로 정렬하면 되는 줄 알았다. 하지만 그렇게 코드를 작성할 경우 input이 [3, 30, 34, 5, 9]일 경우 output이 9534330가 아니라 9543330가 된다는 것을 발견했다.

 

원인을 분석해보니 내 알고리즘은 주어진 정수를 그 자체가 아니라 자리수로 나눠서 다룬다는 것을 꺠달았다. 예를 들면 정수 43이 주어지면 내 알고리즘은 43으로 취급하지 않고 4와 3으로 취급했던 것이다. 주어진 정수를 그 자체로 취급하기 위한 무언가가 필요했다.

 

주어진 정수를 그 자체로 다루기 위해서는 주어진 정수를 따로 담는 자료구조가 필요하다고 생각했다. 그래서 ArrayList를 사용하기로 했다. 왜냐하면 ArrayList는 주어진 정수를 따로 담을 수 있을 뿐만 아니라 정렬도 가능했기 때문이다.

 

import java.util.ArrayList;
import java.util.Comparator;

class Solution {
    public String solution(int[] numbers) {
        String answer = "";
        ArrayList<String> numList = new ArrayList<>();
        
        for(int num : numbers) { 
            numList.add(Integer.toString(num));
        }
        
        numList.sort(Comparator.reverseOrder());
        
        for(String num : numList) {
            answer += num;
        }

        return answer;
    }
}

 

그래서 위와 같이 코드를 작성한 뒤 실행했다. 생각했던대로 정수 그 자체는 보존되었다. 하지만 input [3, 30, 34, 5, 9]에 대하여 9534330가 아니라 9534303을 return했다.

 

문제 원인을 분석하다가 '혹시 앞 자리 수가 같다면 자릿수가 작을수록 우선순위를 높여야 하는건가?'라는 생각을 했다. 즉, [30, 3]이 input으로 주어진다면 3이 30보다 자릿수가 작기 때문에 앞으로 와서 303이 아니라 330을 return하는 것이다. 하지만 이내 생각해보니 [34, 3, 30]이 input으로 주어질 경우 34330을 return해야 하는데 저 알고리즘을 사용하면 33430을 return해서 알고리즘이 옳지 않다는 것을 알 수 있었다.

 

도저히 해결방법을 모르겠어서 아래 링크에서 다른 분의 코드를 참고했다. 이 분에 따르면 String 상태에서 A+B와 B+A를 비교해서 내림차순으로 정렬하고나서 마지막이 000..인 예외 경우만 처리하면 된다고 하셨다.

https://programmers.co.kr/learn/questions/9355

 

나는 무엇을 배웠나

 

내가 Comparator 사용법에 익숙하지 못 하다는 것을 알게 되었다. 그래서 아래 블로그를 통해 공부했다.

https://gmlwjd9405.github.io/2018/09/06/java-comparable-and-comparator.html

https://www.daleseo.com/java-comparable-comparator/