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

• 수의 범위가 작다면 카운팅 정렬을 사용하여 더욱 빠르게 정렬할 수 있습니다.
  https://www.acmicpc.net/problem/10989

1. 문제

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

2. 문제 접근

1) 수의 개수 N을 입력받는다.
2) N만큼 반복하면서 정수를 입력받고 이때 max 변수를 이용하여 입력받는 정수의 최대값을 저장한다. 입력받은 정수를 배열에 저장한다.
3) 카운팅 정렬을 이용하여 새로운 배열에 값들의 위치에 대한 index를 저장한다.
4) 새로운 배열을 이용하여 입력받은 정수를 출력한다.

 

• 카운팅 정렬 : 카운팅 정렬은 각 배열 원소끼리 직접 비교하는 것이 아닌, 인덱스를 갖고 위치를 찾아나가는 정렬 알고리즘.

3. 코드

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

//카운팅 정렬 사용
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int max = 0;
        int arr[] = new int[N];
        StringBuilder sb = new StringBuilder();
        for(int i =0;i<N;i++) {
            arr[i] = Integer.parseInt(br.readLine());
            if(max<arr[i])
                max=arr[i];
        }
        int count[] = new int[max+1];
        for(int i=0;i<N;i++) {
            count[arr[i]]++;
        }
        for(int i=1;i<count.length;i++) {
            count[i] += count[i-1];
        }
        for(int i=1;i<count.length;i++) {
            for(int j=count[i-1];j<count[i];j++) {
                sb.append(i).append("\n");
            }
        }
        System.out.print(sb);
    }
}