[백준] 10989_수정렬하기3 / 카운팅 정렬

 

Bronze

 

문제

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

 

입력

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

 

출력

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

---

풀이

import java.util.*;
import java.io.*;

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[] count = new int[10001]; 
        
        // 카운팅 정렬
        for(int i=0; i<N; i++){
            int index = Integer.parseInt(br.readLine());
            count[index] += 1;
        }
        for(int i=0; i<count.length; i++){
            while(count[i]>0){
                sb.append(i).append("\n");
                count[i]--;
            }
        }
        
        System.out.print(sb);
        br.close();
    }
}

 

 

카운팅 정렬

각 값의 빈도를 계산하여 카운팅 배열에 저장한 후, 누적 빈도를 통해 배열을 정렬한다.
데이터의 범위가 작을 때 매우 빠르고 메모리 효율적인 정렬 방법이다. 

 

[4, 2, 2, 8, 3, 3, 1] 
=> 카운팅 배열 : [0, 1, 2, 2, 1, 0, 0, 0, 1]
=> 누적 배열  : [0, 1, 3, 5, 6, 6, 6, 6, 7]
=> 정렬된 배열 : [1, 2, 2, 3, 3, 4, 8]

 

 

 

• 최대 값 찾기: 입력 배열에서 가장 큰 값을 찾는다. 이는 카운팅 배열의 크기를 결정하는 데 필요하다. 
• 카운팅 배열 생성: 각 값의 빈도를 저장할 카운팅 배열을 생성한다. (최댓값+1)
• 빈도 계산: 입력 배열을 순회하며 각 값의 빈도를 카운팅 배열에 저장한다.
• 누적 빈도 계산: 각 값을 누적하여 각 값이 정렬된 배열에서 위치할 인덱스를 계산한다.
• 정렬된 배열 생성: 입력 배열을 순회하며 누적배열을 통해 정렬된 배열을 생성한다.

 

 

---

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