[JAVA] 백준 10989번 수 정렬하기 3 : 카운팅 정렬 (Counting Sort)

10989번: 수 정렬하기 3

 

1. 문제 추상화

 

N개의 수를 오름차순 정렬 하시오.

 

2. 알고리즘

 

카운팅 정렬을 사용하는 문제이다. 

 

카운팅 정렬은 퀵, 병합, 힙 정렬같이 복잡하지 않고 단순하고 직관적이다. 시간복잡도도 O(N)으로 굉장히 빠르다. 이해하기 쉽고 빠르다는 장점이 있지만 많은 수의 정렬은 힘들다.

 

 

1. 입력받은 N개의 수를 배열에 저장하고 제일 큰 값을 구한다. 

 

2. 제일 큰 값이 10이므로 배열의 크기가 ( 10 + 1 )인 카운팅 배열 하나를 생성한다. 

 

3. 입력받은 수와 대응하는 인덱스가 가리키는 값을 1 증가한다. 2는 두 개이므로 카운팅 배열의 인덱스 2의 값은 2이다.

 

4. 카운팅 배열에서 값인 0인 경우를 제외하고 인덱스를 인덱스의 값만큼 반복 출력한다. ( 결과 : 1 2 2 4 7 8 8 10 )

 

 

3. 코드

 

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

public class Main {
	
	private static BufferedReader br;
	private static BufferedWriter bw;
	private static StringBuilder sb;
	
	private static int[] inputArr;
	private static int[] countingArr;

	public static void main(String[] args) throws NumberFormatException, IOException {
		createObjects();
		makeArr();
		initializeArr();
		doCountingSort();
		printCountingArr();
		closeBuffedIO();
	}
	
	public static void createObjects() {
		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		sb = new StringBuilder();
	}
	
	public static void makeArr() throws NumberFormatException, IOException {
		int size = Integer.parseInt(br.readLine());
		inputArr = new int[size];
	}
	
	public static void initializeArr() throws NumberFormatException, IOException {
		for(int i =0; i< inputArr.length; i++) {
			inputArr[i] = Integer.parseInt(br.readLine());
		}
	}
    
   	public static void doCountingSort() {
		int size = getMaxOnInputArr();
		countingArr  = new int[size+1];
		
		for(int i =0; i< inputArr.length;i++) {
			countingArr[inputArr[i]]++;
		}
	}
	
	public static void printCountingArr() throws IOException {
		for(int i=0; i<countingArr.length; i++) {
			if(countingArr[i] != 0) {
				for(int j =0; j< countingArr[i]; j++) {
					sb.append(i).append("\n");
				}
			}
		}
		bw.write(sb.toString());
		bw.flush();
	}
    
   	public static int getMaxOnInputArr() {
		int max = 0;
		for(int value : inputArr) {
			if( value > max ) {
				max = value;
			}
		}
		return max;
	}
	
	public static void closeBuffedIO() throws IOException {
		bw.close();
		br.close();
	}

}