백준 10989번: 수 정렬하기 3

문제 링크

Dual-Pivot Quick Sort를 이용하는 Arrays.sort를 사용해도 아슬아슬하게 정답인정은 되긴 하나, 입력 가능한 수의 최대 갯수가 입력받는 수의 범위보다 월등히 작으므로 Counting Frequency를 입력할 배열을 생성하여 푸는 것이 입력받는 수가 많아질수록 훨씬 빠르다.

자바를 이용한 풀이

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

public class BaekJoon10989 {
	
	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));
		
		int n = Integer.parseInt(br.readLine());
		int[] cnt = new int[10001];					//10000보다 작거나 같은 자연수이므로
													//10000까지 카운팅할 배열 생성
		for(int i = 0; i < n; i++) {
			cnt[Integer.parseInt(br.readLine())]++; //입력받은 수의 배열 인덱스에 +1
		}
		
		for(int i = 1; i <= 10000; i++) {
			while(cnt[i] > 0) {						//카운팅이 1 이상이라면 
				bw.write(i + "\n");					//해당 수를 출력하고
				cnt[i]--;							//배열에서 카운팅 -1
			}
		}
		
		bw.flush();
	}
}