[백준] 수 정렬하기 3 10989 - JAVA

문제

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

풀이

Arrays.sort() 만 쓰다보니 Arrays.sort() 에만 익숙해졌다.😥

문제를 보면 N이 10,000,000 까지 간다. 메모리 초과가 일어날 수도 있고 간당간당하게 통과될수도 있다.

따라서 Counting Sort 를 이용한다.

10000 이하의 수가 입력이 된다.

따라서 배열의 크기를 10001 로 선언한다.

그리고 입력되는 수가 index가 되고 입력되는 숫자가 등장하는 만큼 배열의 값을 증가시킨다.

그리고 1부터 배열의 값만큼 출력하면된다.

코드

import java.io.*;
import java.util.Arrays;

class Main {
	public static void main(String args[]) throws Exception{
		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())]++;
		}
		
		for(int i=1;i<10001;i++) {
			while(count[i] > 0) {
				sb.append(i).append("\n");
				count[i]--;
			}
		}
		System.out.print(sb);
	}
}