[백준] 2751번 수 정렬하기2(Java)

해결

• 정렬문제를 풀 때, Java에서 기본적으로 제공해주는 Arrays.sort()를 사용하였다. 해당 문제에서도 동일하게 Arrays.sort()를 사용하여 문제를 풀었는데, 소요시간이 아주 오래 걸렸다. 잘 하면 시간제한에 걸릴 것 같았다.
• Arrays.sort()는 dual-pivot Quicksort 알고리즘을 사용하여, 평균 시간복잡도가 O(nlogn) 으로 빠른 알고리즘이지만, 최악의 경우 시간복잡도가 *O(n^2) 이다.
• 그래서 해당 문제를 풀 때, 최악의 경우에도 O(nlogn) 이거나, O(n)에 가까운 알고리즘을 사용해야 한다고 검색해보니 나왔다.
• 정렬 알고리즘 중 시간 복잡도가 O(n)인 Counting Sort(계수 정렬)을 사용하여 문제를 풀어보기로 했다.

[참고] Counting Sort 정리
https://velog.io/@dayoung_sarah/알고리즘Counting-Sort-계수-정렬

코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int cnt = Integer.parseInt(br.readLine());

        int[] arr = new int[cnt];
        for(int i=0; i<cnt; i++) {
            int num = Integer.parseInt(br.readLine());
            arr[i] = num;
        }

		// 입력값의 범위가 절대값이 1000000이기에 범위는 2000000이다.
        int range = 2000000;
        int[] sortedArray = countingSort(arr, range);

        StringBuilder sb = new StringBuilder();
        for (int num : sortedArray) {
            sb.append(num + "\n");
        }

        System.out.println(sb);
    }

    public static int[] countingSort(int[] arr, int range) {
        int[] countingArray = new int[range + 1];
        int[] sortedArray = new int[arr.length];

		// 원소의 범위가 -100000~100000으로 각 value에 1000000을 더해준다. 
        for(int value : arr) {
            countingArray[value+1000000]++;
        }

        for(int i=1; i<countingArray.length; i++) {
            countingArray[i] += countingArray[i-1];
        }

        for(int i=arr.length-1; i>=0; i--) {
            sortedArray[--countingArray[arr[i]+100000]] = arr[i];
        }

        return sortedArray;
    }
}