[백준] java 10989

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

문제

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

접근 방법 / 풀이 과정

다음은 문제에서 주어진 조건이다.

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

나는 문제에서 오름차순으로 정렬하는 것을 요구하니 당연히 정렬 알고리즘을 구현하려다, 자연수의 범위가 10,000이라는 것에 무언가 아이디어가 떠올랐다.
아마 이 기발한 아이디어가 떠오른 요인으로는 문제에서 주어진 조건, 그리고 문제 설명에 있었던 것 같다. 문제 설명에는 이렇게 나와있다.

수의 범위가 작을 때 카운팅 정렬을 사용하면 더욱 빠르게 정렬할 수 있다.

아이디어는 이렇다. 10001개의 배열을 만든다. 그리고 입력값을 배열의 인덱스 번호로 인식하고, 값을 1 상승시킨다.
자, 10001개의 배열을 순회시켜보자. 입력값을 인덱스 번호로 인식 시키고 안의 값을 1 상승시킨다고 하였다. 검사한 인덱스의 값이 0보다 크다면, 인덱스 번호에 해당하는 입력이 들어왔다는 이야기이다.
안의 값만큼 출력시킨다.

import java.io.*;

public class Main{
   public static void main(String[] args) throws IOException 
   { 
	   BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	   BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	  int N = Integer.parseInt(bf.readLine());
	  int[] array = new int[10001];
	  for(int i = 0; i < N; i++) 	
		 array[Integer.parseInt(bf.readLine())]++; 
	  
	  for(int i = 0; i < array.length; i++) 
	  {
		  if(array[i] > 0)
		  {
			  if(array[i] > 1)
			  {
				  for(int j = 0; j < array[i]; j++)
					  bw.write(i+"\n");
			  } 
			  else 			 			  
				  bw.write(i + "\n");			  
		  }
	  }
	  bw.flush();
   }  
}     
     

느낀점 / 배운점

위에서 사용한 로직은 사실 알게 모르게 많이 사용했었던 것 같다. 구글링을 통해 이는 카운팅 정렬의 원리인 것을 확인할 수 있었다. 카운팅 정렬에 대해서 더 알아보고 정리 해두려고 한다.