[백준 10989번: 수 정렬하기3] 자바 문제풀이(카운팅 정렬)

"수의 범위가 작다면 카운팅 정렬을 사용하여 더욱 빠르게 정렬할 수 있습니다."

문제 힌트대로 카운팅 정렬을 이용해서 풀어보았다.

 

*카운팅 정렬 : 각 항목이 몇 개씩 있는지 세어서 정렬하는 알고리즘으로 시간복잡도 O(n)으로 굉장히 빠르다.

ㅎㅎ발그림으로 설명해보았다.

인자에 대응하는 배열에 인자 개수만큼 저장하고 세는 알고리즘이므로 같은 수가 중복 입력되어도 정렬이 된다.

 

만약 수의 범위가 정해져있고 정렬 값을 출력만 하면 된다면 다음과 같이 간단하게 코드를 사용할 수 있다.

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


public class Main {
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder st = new StringBuilder();
		int N = Integer.parseInt(br.readLine());
		int counting[]= new int[10001];
		
		for(int i=0; i<N; i++)
			counting[Integer.parseInt(br.readLine())]++;
		
		for(int i=1; i<=10000; i++) {
			while(counting[i]>0) {
				st.append(i).append('\n');
				counting[i]--;
			}
		}
		System.out.print(st);
		br.close();
	}

}

 

오랜만에 복학해서 다시 자료구조를 들여다보려니 머리가 아프다..