[백준 알고리즘] Q10989 수 정렬하기 3 -Counting Sort (계수 정렬)

1. Java 구현

(1) Arrays.sort 정렬 사용

import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException {
		/* 2018.08.09 */
		int N = Integer.parseInt(br.readLine());
		int[] numArr = new int[N];
		
		getInput(numArr, N);
		
		sortArray(numArr);
		
		printList(numArr);
		
		bw.close();
		br.close();
	}
	
	public static void getInput(int[] arr, int n) throws IOException {
		for(int i = 0; i < n; i++) {
			int num = Integer.parseInt(br.readLine());
			arr[i] = num;
		}
	}
	
	public static void sortArray(int[] arr) {
		Arrays.sort(arr);
	}
	
	public static void printList(int[] arr) throws IOException {
		for(int i = 0; i < arr.length; i++) {
			//bw.write(list.get(i) + "\n");
			sb.append(arr[i] + "\n");
		}
		bw.write(sb.toString());
	}

}

(2) TreeMap 사용

          
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        TreeMap tm = new TreeMap<>();
        for(int i = 0; i < n; i++) {
            int num = sc.nextInt();
            tm.put(num, tm.containsKey(num) ? tm.get(num) + 1 : 1);
        }

        Iterator it = tm.keySet().iterator();
        StringBuilder sb = new StringBuilder();
        while(it.hasNext()) {
            int key = it.next();
            int value = tm.get(key);
            for (int i = 0; i < value; i++) {
                sb.append(key).append("\n");
            }
        }
        System.out.println(sb.toString());

    }
}

(3) CountingSort 정렬 사용

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[10000 + 1];
		for(int i = 0; i < n; i++) 
			arr[Integer.parseInt(br.readLine())]++;
		
		int sum = 0;
		int index = 0;
		for(int i = 0; i < n;) {
			if(i < sum + arr[index]) {
				sb.append(index).append("\n");
				i++;
			}
			if(i == sum + arr[index]) {
				sum += arr[index];
				index++;
			}
			
		}
		
		bw.write(sb.toString());
		bw.close();

	}

}

2. 코드설명

 세가지 방식으로 문제를 풀었다.

 첫번째 방식은 Arrays.sort 라는 자바에서 제공하는 기능을 활용했다. 이 정렬방식의 시간복잡도는 O(nlogn) 이다. 그리고 제공되는 기능을 사용하기 때문에 

 코드 구현이 간결하고 편했다. 두번째 방식은 TreeMap 을 사용했다. TreeMap은 키의 값에 맞추어 자동으로 정렬된다. 그러기 때문에 별도에 정렬은 하지 않고

 TreeMap에 값을 순차적으로 출력하면 된다. 하지만 TreeMap은 Key값이 중복이 되지 않기 때문에 값의 갯수를 value에 넣어야 한다. 

 그러다보니 구현을 했을 때, 시간복잡도 O(n^2)이 되었다. 세번째 방식은 Counting Sort를 활용했다. 만약 입력받는 수의 범위가 정해져있지 않거나, 소수를

 포함한 수였더라면, 이 정렬 방법을 활용할 수 없다. 그러나 문제에서는 10,000 까지라는 제한조건이 있어 활용이 가능했다.

 코드를 예를 들어 설명하자면, 1이 5개라면 arr[1]에 5를 저장하고, 20이 2개라면 arr[20]에 2를 저장한다. 그리고 각 배열을 순환해서 그 갯수 만큼 출력한다.

 이 방법은 시간복잡도가 O(n)이가 가장 빠르다. Counting Sort에 대한 정렬방법은 다음에 추가로 정리를 할 예정이다. 

3. Pain Point

 숫자의 갯수만큼 출력을 하는데 ... 시간복잡도를 O(n)으로 구현하는 것에 많은 애를 먹었다. 그래서 생각한게 TreeMap을 사용해서 하는 것이었다.

 하지만 이 또한, O(n)이 되지 않았고.... 정말 고민 많이 했다...