[JAVA] 백준 10989번 - 수 정렬하기 3(카운팅 정렬)

 

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

10989번: 수 정렬하기 3

 

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

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());

        int[] arr = new int[10001]; // 수는 10000보다 같거나 작은 자연수

        for(int i=0; i<n; i++){
            arr[Integer.parseInt(br.readLine())]++; // 입력받은 수의 인덱스 값을 1증가
        }

        for(int i=1; i<10001; i++){ // 자연수이므로 1부터 시작
            while(arr[i]>0){ // 해당 인덱스 값의 수(빈도수)가 0이 될때까지 1씩 감소하며 출력
                sb.append(i+"\n");
                arr[i]--;
            }
        }
      System.out.println(sb);
    }
}

 

 

카운팅 정렬을 이용하는 문제다.

수를 입력받을 때에 입력받은 수에 해당하는 배열의 인덱스 값을 1씩 증가시킨다.

예제 입력에 나와있는 예시대로 한다면 아래와 같은 배열이 생긴다.

 

1	2	3	4	5	6	7	8	9
2	2	2	1	2	0	1	0	0

 

 

인덱스는 이미 오름차순이고, 각각의 원소들은 입력받은 수(인덱스)의 빈도수라고 볼 수 있으므로

배열 원소값의 빈도수를 하나씩 감소시키며 출력하면 된다.