[JAVA] 백준 10898 수 정렬하기 3

10989번: 수 정렬하기 3 (acmicpc.net)

10989번: 수 정렬하기 3

 

풀이 과정 

 

- 도수 정렬(counting sort) 이용 

 

- 도수 정렬은 데이터를 비교, 교환하는 작업이 필요 없어 매우 빠름

- 다중 for문이 아닌 단순 for문만을 사용하고, 재귀 호출과 2중 for문이 없으므로 아주 효율적인 알고리즘

- 하지만 도수 분포표가 필요하기 때문에 데이터의 최솟값과 최댓값을 미리 알고 있는 경우에만 사용 가능 

2023.08.01 - [C언어/자료구조] - 6-9장 도수 정렬

6-9장 도수 정렬

 

 

정답

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

public class Main {
    //카운팅 정렬
    static void countingSort(int[] a, int n, int max)
    {
        int f[] = new int[max+1]; //누적 도수 
        int b[] = new int[n]; //작업용 목표 배열 
        
        for(int i=0; i<n; i++)
        {
             f[a[i]]++;
        }
        for(int i=1; i<=max; i++)
        {
             f[i]+=f[i-1];  
        }
        for(int i=n-1; i>=0; i--)
        {
            b[--f[a[i]]] = a[i];
        }
        for(int i=0; i<n; i++)
        {
            a[i]=b[i];
        }
    }
    
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int num = Integer.parseInt(br.readLine());
        int n[] = new int[num];
        
        for(int i=0; i<num; i++)
        {
            n[i] = Integer.parseInt(br.readLine());
        }
        
        int max = n[0];
        for(int i=1; i<num; i++)
        {
            if(n[i]>max)
                max=n[i];
        }
      
        countingSort(n,num,max);
        
        for(int i=0; i<num; i++)
        {
            bw.write(Integer.toString(n[i])+"\n");
        }
        
        bw.flush();
        bw.close();

    }
}