백준 10989번

수 정렬하기 3

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력

풀이

우선 처음에 이 문제를 풀때 단순히 쉽게 해결 하려고 Scanner과 Arrays.sort()를 사용했고 결과를 for문을 활용해서 출력하려 했다.

>

그러나 시간 제한이 발생했고 이를 줄여야 했다.

그래서 찾아보니, Scanner를 쓰면 내부적으로 자체 정규식 검사 과정에서 시간이 엄청 소요되고, StringBuilder가 시간 소요가 적다고 한다.

또한 Arrays.sort() 의 경우 dual-pivot Quick sort 알고리즘을 사용하여 평균 O(nlogn) 의 시간복잡도를 보이지만 최악의 경우 O(n2) 로 좋지 않는 성능이 될 수도 있다고 한다.

우선 Scanner 대신 BufferedReader을 사용하고, Arrays.sort() 대신 카운팅 정렬 알고리즘을 사용해야 한다. 결과는 for문 대신 StringBuilder을 사용해서 시간 제한에 걸리지 않도록 했다.

카운팅 정렬 알고리즘의 시간복잡도는 O(N + K) 이다. K는 자릿수를 의미하는데 입력데이터가 K 보다 훨 씬 큰경우. 즉 데이터가 많으면 많을 수록 O(N) 에 가깝기 때문에 이상적으로는 O(N) 이라고 보아도 무방하다고 한다.

코드

import java.io.*;

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