[백준/Java] 10989번 :: 수 정렬하기 3

| 문제

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

 

| 입력

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

 

| 출력

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

 

| 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main
{
	public static void main(String[] args) throws NumberFormatException, IOException 
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		
		for(int i=0; i<N; i++)
			arr[i] = Integer.parseInt(br.readLine());
		
		Arrays.sort(arr);
		
		
		for(int i=0; i<arr.length; i++)
			sb.append(arr[i]).append("\n");
				
		System.out.print(sb);
	}
}

 

 

| 정리

문제를 풀고 나서 발견한 아래 내용

카운팅 정렬이 뭐지,,? 싶어서 찾아봤고 입력 받은 수를 배열에 저장하는 것이 아닌

해당하는 값과 일치하는 배열의 방에 값을 카운팅 해주는 것이라는 내용을 알았다.

내용을 알고 보니 배웠던 것 같은 기억이 스멀스멀 올라왔다.

만약 입력 받은 수가 1 2 3 5 4 2 라면

0	1	2	3	4	5
0	1	2	1	1	1

 

이렇게 배열이 구성된다는 말!

그래서 아래처럼 카운팅 정렬을 이용해서 풀이를 해보았고, sort보다 성능이 좋게 나온 것을 볼 수 있었다.

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

public class Main
{
	public static void main(String[] args) throws NumberFormatException, IOException 
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[10001];
		
		for(int i=0; i<N; i++)
			arr[Integer.parseInt(br.readLine())]++;
		
		for(int i=0; i<arr.length; i++)
		{
			while(arr[i] > 0)
			{	
				sb.append(i).append("\n");
				arr[i]--;
			}
				
		}
		
		System.out.println(sb);
	}
}