白駿10989号:数列3



質問リンク
ダブルPivotクイックSortのArraysを使用.sortを使用しても正確な答えが得られるのは危険であるが,入力可能な最大数は入力数の範囲よりはるかに小さいため,入力counting Frequencyの数を解放する配列を生成するほど速度が速くなる.

Javaを使用した解答

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();
	}
}