10989번 '수 정렬하기 3'

import java.io.*;

import java.util.*;

class Main {

public static void main(String[] args) throws IOException {

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

StringBuffer stringBuffer = new StringBuffer();

int size = Integer.parseInt(in.readLine());

int[] count = new int[10001];

for(int i=0; i<size; ++i) {

int input = Integer.parseInt(in.readLine());

count[input] += 1;

}

for(int i=0; i<=10000; ++i) {

int repeat = count[i];

if(repeat != 0) {

while(repeat != 0) {

stringBuffer.append(i);

stringBuffer.append("\n");

repeat--;

}

}

}

System.out.println(stringBuffer);

}

}

특정 입력 조건이 있을 때 정렬을 선형시간 내에 할 수 있다.

이 문제에서의 입력 조건이 10000 이하의 자연수이므로

배열에 입력값의 빈도수를 저장하여 출력하는 방식으로 풀 수 있다.

시간초과가 나길래 StringBuffer 클래스를 활용하여 풀었다.

Swift로도 시간 초과.