[백준,BOJ 10989] 수 정렬하기 3( JAVA 구현)

 -풀이

  이 문제에 대한 설명으로 계수 정렬을 사용하라고 나와있다. 계수 정렬은  O(n + k)의 시간 복잡도를 가지며, 여기서 k는 정렬을 해야하는 데이터 중 가장 큰 값을 의미한다. 만약 k가 n보다 작은 수이면 O(n)이 되지만, k가 n보다 매우 큰 수이면 O(무한)이 될 수도 있다. 예를 들어 10개의 숫자를 정렬하는 데, 가장 큰 숫자가 100일 경우, O(n^2)이 된다. 100(k)은 10(n)의 제곱이므로. 1000이면 O(n^3)이 된다. 즉 정렬할 수들의 최댓값에 영향을 받는 알고리즘이라고 볼 수 있다.

 

  즉, 정렬해야 하는 데이터의 범위가 적을수록 효율적인 성능을 보여주는 알고리즘이라 할 수 있다. 그리고 실제로 이 문제에서는 이전 수 정렬하기2 문제의 데이터 범위인 1,000,000과는 다르게 10,000이라는 작은 범위의 데이터가 입력으로 주어진다는 사실을 알 수 있다. 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

class Main {
  public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    int n = Integer.parseInt(br.readLine());
    int arr[] = new int[n]; // 데이터 저장 배열
    int count[] = new int[10001]; // 데이터의 범위 배열, 데이터가 등장하는 횟수를 카운트한다., 등장할 수 있는 데이터의 최댓값 만큼 배열을 선언해주어야 한다.
    int result[] = new int[n]; // 최종 정렬 데이터가 저장될 배열
    
    for(int i=0;i<arr.length;i++) { // 데이터를 입력받는 반복문
    	int num = Integer.parseInt(br.readLine());
    	arr[i] = num; // 데이터를 데이터 저장 배열에 저장
    	count[num]++; // 해당 데이터를 인덱스로 사용하여 등장하는 횟수를 증가시킨다. 
    }
    
       
    for(int i=1;i<count.length;i++) { // 데이터의 등장횟수를 누적합하여 구한다.
    	count[i]+=count[i-1];
    }
    
    for(int i = arr.length-1;i>=0;i--) { // 데이터의 배열 마지막 인덱스부터 반복한다.
    	result[--count[arr[i]]] = arr[i]; // 최종 정렬 배열에 정렬한다.
    }
    
    for(int i=0;i<result.length;i++) { // 출력
    	bw.write(String.valueOf(result[i])+"\n");
    }
    
    
    bw.flush();
    bw.close();
    
  }
}

  계수 정렬에 대한 자세한 설명은 아래의 블로그를 참고하면 좋을 것 같다. 

Counting Sort : 계수 정렬

  또한 위의 블로그에서도 확인할 수 있는 내용으로 데이터를 인덱스로 하여 등장횟수를 카운팅 한 배열을 순서대로 꺼내는 방식 또한 정렬을 할 수 있지만, 데이터의 범위 사이의 간극이 클수록 비효율적이기 때문에 위와 같은 방식으로 정렬하는 것이 좋다고 한다.