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

가장 큰 수

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

프로그래머스

 

풀이 방법

주어진 수를 조합하여 가장 큰 수를 만드는 경우의 수 문제라 착각할 수 있지만 정렬 문제이다.
수를 비교하여 가장 큰 수가 되는 조건식을 세워서 배열을 정렬하여 출력하는 문제다.

조건식은 다음과 같다.

1. 두 수를 앞 자리부터 비교한다.
2. 해당 자리의 수가 같을 경우 두 수의 자릿수를 비교한다

문제의 예시 [6, 10, 2] 로 비교하자면
6과 10을 비교했을 때 앞 자리부터 비교(6, 1)한다. 6이 1보다 크므로 교체하지 않고 그대로 둔다.
10과 2를 비교했을 때 앞 자리부터 비교(1, 2)한다. 1이 2보다 작으므로 교체한다.
최종적으로 [6, 2, 10] 이 되어 6210을 도출할 수 있다.

2번의 경우는 [3, 300, 30] 의 예시를 들어보자.
3과 30을 비교했을 때 앞 자리부터 비교(3, 3)한다. 두 수가 같으므로 자릿수를 비교해 교체하지 않는다.
300과 30을 비교했을 때 앞 자리부터 비교(3, 3)한다. 두 수가 같으므로 자릿수를 비교해 교체한다.
따라서 최종적으로 [3, 30, 300] 이 되어 330300이라는 가장 큰 수가 나올 수 있는 것이다.

코드로 표현하려면 두 수를 문자열로 변환하고 각각 index를 생성하여 해당 index의 값을 비교하고 index가 각 문자열의 길이를 초과했는지로 자릿수를 판별하면 된다.

근데 이렇게 귀찮고 복잡하게 비교하지 않고 compareTo를 활용하면 된다.
두 수 a와 b를 받아 각각 문자열로 변환한 다음 a b인 경우와 b a인 경우를 비교하면 된다.
즉, 6과 10이 들어왔을 경우 문자열로 변환하여 "610"과 "106"을 compareTo로 비교하면 의도했던 것과 똑같이 동작한다.

비교 기준을 세웠으니 어떻게 정렬할 지를 선택해야 한다.
문제에서 numbers의 길이는 10만 이하, 원소는 1,000 이하라고 한다.
문자열로 변환해 비교하기 때문에 메모리 초과가 발생할 수 있어 최대한 정렬 연산을 줄여야 했다.
따라서 퀵 정렬 방식으로 정렬하였다.

퀵 정렬은 워낙 많이 알려진 정렬 알고리즘이고 자세히 정리된 글이 많으니 간단히 정리하면
주어진 배열을 기준값을 통해 분할하여 최대한 정렬 연산을 줄이는 기법으로 배열의 시작, 중간, 끝 중 하나를 선택해 기준값을 잡고 재귀 함수를 통해 계속 반복 분할하여 swap하며 정렬하는 방식이다.
(꽤 오랜만에 써봐서 찾아보고 쓰는데 시간을 좀 썼다)

나는 중간을 기준으로 나누었다.
찾아보니 퀵 정렬에서 최악의 경우는 거의 정렬된 혹은 완전히 정렬된 배열인데
N개의 배열에서 한쪽 끝을 기준으로 삼을 경우 N-1로 분할하기 때문에 O(N^2)라는 최악의 성능을 낸다고 한다.
하지만 중간 값을 선택할 경우 왼쪽과 오른쪽이 균등하게 분할되기에 완전 최악의 경우를 제외하고서는 O(N) ~ O(NlogN)의 성능을 내기 때문에 중앙값(혹은 랜덤값)을 선택하는 것이 평균적으로 의도한 성능대로 동작할 것이다.

소스 코드

    class Solution {
        public String solution(int[] numbers) {
            String answer = "";

            quicksort(numbers, 0, numbers.length - 1);

            for (int number : numbers) {
                if(answer.isEmpty() && number == 0) {
                    continue;
                }

                answer += String.valueOf(number);
            }

            if(answer.isEmpty()) {
                answer = "0";
            }

            return answer;
        }

        // 퀵 정렬
        // 중간 요소를 pivot으로 설정
        public void quicksort(int[] numbers, int start, int end) {
            if(start >= end) {
                return;
            }

            int pivot = partition(numbers, start, end);

            quicksort(numbers, start, pivot);
            quicksort(numbers, pivot + 1, end);
        }

        public int partition(int[] numbers, int start, int end) {
            int pivot = numbers[(start + end) / 2];
            int l = start - 1;
            int r = end + 1;

            while (true) {
                do {
                    l++;
                } while (compare(numbers[l], pivot));

                do {
                    r--;
                } while (l <= r && compare(pivot, numbers[r]));

                if(l >= r) {
                    return r;
                }

                int tmp = numbers[l];
                numbers[l] = numbers[r];
                numbers[r] = tmp;
            }
        }

        public boolean compare(int a, int b) {
            String ab = String.valueOf(a) + String.valueOf(b);
            String ba = String.valueOf(b) + String.valueOf(a);

            return ab.compareTo(ba) > 0;
        }
    }