[프로그래머스][lv.1][정렬] - 정수 내림차순으로 배치하기

 

함수 solution은 정수 n을 매개변수로 입력받습니다. n의 각 자릿수를 큰것부터 작은 순으로 정렬한 새로운 정수를 리턴해주세요. 예를들어 n이 118372면 873211을 리턴하면 됩니다.

 

[제한 조건]

• n은 1이상 8000000000 이하인 자연수입니다.

class Solution {
    /**
     * 118372 -> 873211
     */

    public long solution(long n) {
        char[] nToCharArr = String.valueOf(n).toCharArray();
        
        // 제약조건이 8,000,000,000이하의 자연수니까 long 써야함
        long[] longArr = new long[nToCharArr.length];

        for (int i = 0; i < nToCharArr.length; i++) {
            longArr[i] = Long.parseLong(String.valueOf(nToCharArr[i]));
        }

        int startIdx = 0;
        int endIdx = longArr.length-1;
        
        // 퀵 정렬
        quickSort(longArr, startIdx, endIdx);

		// 정렬된 배열을 StringBuilder로 문자열로 만들기
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < longArr.length; i++) {
            sb.append(longArr[i]);
        }

		// StrigBuilder로 만든 문자열을 다시 형변환하여 리턴
        return Long.parseLong(sb.toString());
    }

    private void quickSort(long[] arr, int start, int end) {
        int p = partition(arr, start, end);
        if(start < p - 1) quickSort(arr, start, p-1);
        if(end > p) quickSort(arr, p, end);
    }

    private int partition(long[] arr, int start, int end) {
        long pivot = arr[(start + end) / 2];

        while (start <= end) {
            while(arr[start] > pivot) start++;
            while(arr[end] < pivot) end--;

            if (start <= end) {
                long tmp = arr[start];
                arr[start] = arr[end];
                arr[end] = tmp;

                start++;
                end--;
            }
        }
        return start;
    }

}

---

정렬 - 퀵 정렬