[정렬] 시간복잡도 O(N)를 가진 정렬 풀이법

basic : Scanner + Arrays.sort

Scanner는 시간을 많이 잡아먹는데다,

Arrays.sort는 평균 O(nlogn) 지만 최악의 경우 O(n2)

까지도 올라간다.

 

=>BufferedReader, BufferedWriter(or StringBuilder) + Counting Sort

 

다만, Counting Sort가 많이 쓰이지 않는 이유는 K가 정렬할 수들 중에서 가장 큰 값을 의미하는데,만약 K가 N보다 작은 수이면 O(N)이 되지만, K가 N보다 매우 큰 수라면 시간복잡도가 엄청 커질 수 있다.예를 들어 10개 숫자 정렬하는데 가장 큰 숫자가 100일 경우엔 O(N^2)가 되고, 1000이라면 O(N^3)이 된다.즉, 정렬할 수들의 최대값에 영향을 받는 알고리즘이다.

따라서 정렬할 수들의 최대값이 N보다 작은 수 일때 사용하면 좋은 정렬 알고리즘이다.

 

문제)

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어지고

둘째 줄부터 N개의 줄에는 수가 주어지는데 이 수는 10,000보다 작거나 같은 자연수이다.

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력하는 문제를 간단하게 풀어보자

 

풀이)

정렬할 수들의 최대값이 N보다 작은 수이다.

Counting Sort, 말 그대로 해당하는 수가 인덱스인 배열을 새로 만들고 Counting 해서 그 값을 새 배열에 집어넣는다.

 

소스코드 )

import java.util.*;
import java.io.*;
class Main {
	public StringBuilder solution(int[] count) {
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<10001; i++) {
			while(count[i] > 0) {
				sb.append(i).append('\n');
				count[i]--;
			}
		}
		return sb;
    }

	public static void main(String[] args) throws IOException {
		Main T = new Main();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int[] count = new int[10001];
		int n = Integer.parseInt(br.readLine());
		for(int i=0; i<n; i++) {
			count[Integer.parseInt(br.readLine())]++;
		}
		br.close();
		System.out.print(T.solution(count));
	}
}