JAVA 백준 문제풀이 (23) 10989 : 수 정렬하기3

 

백준에서는 계수 정렬(Counting sort)로 풀 것을 권장하고 있으나, 궁금해서 각각 실험해본 결과 퀵정렬과 병합정렬로도 3초 내에 통과할 수 있었다. 빠르기는 계수 정렬이 가장 빠르기는 했다.

 

 

차례로 계수 정렬, 퀵 정렬, 병합 정렬(내장)이다. 

근데 계수 정렬에는 치명적인 단점이 있어서 알고리즘 풀이용으로는 거의 쓰이지 않는다고 한다.

 

일단 계수 정렬이 무엇인지 간단하게 알아보자.

글보다 코드와 그림이 더 와닿을 것이다.

 

 

정렬할 배열의 최대값을 구한 뒤 최대값 만큼의 배열을 만든다. ( array[max+1] )

그리고 정렬할 배열을 체크하며 값을 생성한 배열의 인덱스에 대입해서 카운팅한다.

ex) { 2, 1, 3, 1, 2, 2 }라는 배열을 couting sort를 이용해 체크한다면 2가 세번 나오므로 [2]번 인덱스를 세번 더해서 array[2] = 3이 된다.

 

그리고 카운팅한 배열을 반복문에 넣고 돌려서 새로운 배열에 카운트만큼 인덱스 넘버에 해당하는 값을 넣어주면 된다.

 

언뜻 보면 굉장히 효율적인 정렬 알고리즘처럼 보이겠지만 계수 정렬의 시간복잡도는 O(n+k(최대값))이기 때문에 값이 제한되어 있는 상황이 아니라면 최악의 선택이 될 것이다. 또한 카운트하기위해 만들어야 하는 배열의 크기도 k가 되기 때문에 최대값이 클수록 메모리 낭비도 심하다.

 

쩝.. 그래도 뭐든 알아두면 좋으니 계수 정렬로 풀어보자.

계수 정렬은 구현하기 아주 쉽다.

 

참고로 계수 정렬을 하더라도 StringBuilder나 BufferedReader 둘 중 하나라도 사용하지 않으면 시간 초과가 나온다.

 

 

import java.io.BufferedReader;
import java.io.*;
import java.util.Arrays;

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

        // 입력 받은 값으로 배열 생성
        for (int i=0; i<T; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        // 최대값
        int max = Arrays.stream(arr).max().getAsInt();
        int[] resultArr = new int[max+1];

        // 인덱스에 중복 값 카운트
        for (int i=0; i<arr.length; i++) {
            resultArr[arr[i]]++;
        }

        // 0이 아닐 경우 (카운트 된 적이 있는 인덱스일 경우) 해당 값만큼 인덱스 넘버를 출력
        for (int i=0; i< resultArr.length; i++) {
            if ( resultArr[i] != 0 ) {
                for (int k=0; k<resultArr[i]; k++) {
                    sb.append(i).append('\n');
                }
            }
        }

        System.out.println(sb);
    }
}