[정렬#4] 백준 10989번: 수 정렬하기 3JAVA

10989번: 수 정렬하기 3

문제

---

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

 

 

입력

---

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

 

 

출력

---

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

 

예제 입출력

---

예제 입력	예제 출력
10 5 2 3 1 4 2 3 5 1 7	1 1 2 2 3 3 4 5 5 7

 

풀이

---

 정렬 알고리즘은 여러가지 방법이 있지만, Arrays.sort()로 풀었을 때는 시간초과 판정을 받고, 더 빠른 Collections.sort()로 풀었을 때는 메모리 초과 판정을 받았다.

 따라서 마지막에는 결국 Counting Sort알고리즘으로 문제를 해결했다.

 

코드

---

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

public class Main {
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		int[] count = new int[10000001];
		
		for(int i=0; i<n; i++)
			arr[i] = Integer.parseInt(br.readLine());
		
		for(int i=0; i<n; i++)
			count[arr[i]]++;
		
		for(int i=0; i<10000001; i++)
			for(int j=0; j<count[i]; j++)
				bw.write(i + "\n");
		
		bw.flush();
		bw.close();
	}
	
}