가장 큰 수

문제정의

---

숫자 카드들이 주어지고 이들을 조합하여 가장 큰 수를 만들어 반환하는 문제이다.

문제풀이

---

전체 코드는 다음과 같다.

import java.util.*;

public class BiggestNum {
    
    //프로그래머스 문제풀이 level2 가장 큰 수
    public static void main(String[] args) {
        int[] numbers = {3, 30, 34, 5, 9};
        String[] arr = new String[numbers.length];
        int i = 0;
        for(int n : numbers)
        {
            arr[i++] = String.valueOf(n);
        }
        
        Arrays.sort(arr, new Comparator<String>(){
            @Override
            public int compare(String o1, String o2)
            {
                String s1 = o1 + o2;
                String s2 = o2 + o1;
                Integer i1 = Integer.parseInt(s1);
                Integer i2 = Integer.parseInt(s2);
                
                return i2.compareTo(i1);
                
            }
        });
        StringBuilder buff = new StringBuilder();
        boolean isZero = true;
        for(String s : arr)
        {
            if(Integer.parseInt(s) != 0)
                isZero = false;
            if(!isZero)
                buff.append(s);
        }
        if(buff.length() == 0)
            buff.append("0");
            
        System.out.println(buff.toString());
    }
}

코드는 어렵지 않다. 10-13줄은 int를 문자열로 바꾸어준다. 그리고 이를 정렬하면 되는데, 가장 큰 수를 만들기 위한 정렬은 두 문자를 합쳐보고 더 큰 쪽이 앞에 가도록 하면 된다. 정말 간단하다. 그 부분이 15-26번째 줄이다. 정렬한 문자열을 이제 합쳐주면 되는데 문제 조건을 보면 0이 들어갈 수 있다고 한다. 입력으로 들어온 모든 숫자가 0일 경우를 대비해 isZero를 선언하여 첫 숫자가 0인 것은 들어가지 않도록 했다.

최종 시간복잡도는 numbers의 길이를 n이라 할 때 \(O(nlogn)\)이다.

테스트

질문하기를 보고나서야 푼 문제라서 아쉬움이 남는다. 그래도 하나 배웠는데 compare안에 정렬을 새로 정의할 경우 다중 조건문을 쓰면 혼돈의 정렬이 된다는 것이다(이유는 더 공부가 필요하다.). 질문하기에서 나온 해결방법을 그대로 옮긴거라 필자의 아이디어는 아니지만, compare을 작성할 때 주의해야 할 점을 알았으니 만족한다.