'Do it 자료구조와 함께 배우는 알고리즘 입문' 도서를 토대로 공부하고 관련한 문제를 찾아풀어보고 있습니다.

'도수 정렬' 알고리즘 문제 풀이입니다!!!

문제

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

[나의 풀이1]

• 주어진 배열 => 오름차순 정렬

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

public class Main {

    static int [] countingSort(int [] arr, int N, int max){
        
        // 누적도수
        int [] f = new int[max+1];
        // 작업용 목표 배열
        int [] b = new int[N+1];
    
        // 도수분포표
        for (int i=0; i<N; i++) f[arr[i]]++;
        
        // 누적도수분포표
        for (int i=1;i<=max;i++){
            f[i] += f[i-1];
        }
        // 목표 배열
        for (int i=N-1;i>=0;i--){
            // * -- 연산자 : 참조한 객체의 값을 -1함
            b[--f[arr[i]]] = arr[i];
        }
        //최종 배열
        for (int i=0;i<N;i++) arr[i] = b[i];

        return arr;

    }

    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 N;

        N = Integer.parseInt(br.readLine());
        int [] arr = new int [N];

        for (int i=0;i<N;i++){
            arr[i] = Integer.parseInt(br.readLine());
        }

        // 최댓값 구하기
        int max = arr[0];
        for (int i=1; i<N;i++)
        if (arr[i] > max) max =arr[i];

        arr = countingSort(arr,N,max);

        for (int i=0;i<N;i++){
            bw.write(arr[i]+"\n");
        }
        bw.flush();

    }
}

[나의 풀이2]

• 주어진 배열 => 내림차순 정렬

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

public class Main {

    static int [] countingSort(int [] arr, int N, int max){
     
        // 누적도수
        int [] f = new int[max+1];
        // 작업용 목표 배열
        int [] b = new int[N];
    
        // 도수분포표
        for (int i=0; i<N; i++) f[arr[i]]++;

        // 누적도수분포표
        for (int i=1;i<=max;i++){
            f[i] += f[i-1];
        }

        // 목표 배열
        for (int i=N-1;i>=0;i--){

            // * -- 연산자 : 참조한 객체의 값을 -1함
            // max = 7
            b[(N-1)-(--f[arr[i]])] = arr[i];

        }
        //최종 배열
        for (int i=0;i<N;i++) arr[i] = b[i];

        return arr;

    }

    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 N;

        N = Integer.parseInt(br.readLine());
        int [] arr = new int [N];

        for (int i=0;i<N;i++){
            arr[i] = Integer.parseInt(br.readLine());
        }

        // 최댓값 구하기
        int max = arr[0];

        for (int i=1; i<N;i++)
        if (arr[i] > max) max =arr[i];

        arr = countingSort(arr,N,max);

        for (int i=0;i<N;i++){
            bw.write(arr[i]+"\n");
        }
        bw.flush();


    }
}

도수 정렬은 요소의 대소 관계를 판단하지 않고 빠르게 정렬하는 알고리즘입니다. 순서대로 도수분포표 만들기, 누적도수분포표 만들기, 목표 배열 만들기, 배열 복사하기 단계로 이루어집니다.👨‍🌾👨‍🌾👨‍🌾

도수 정렬 알고리즘은 중첩for문을 사용하지 않아 효율적인 알고리즘이지만 도수분포표가 필요하기 때문에 전체 데이터의 최솟값, 최댓값을 알고 있어야 사용할 수 있다는 장단점이 있습니다.🏄🏄🏄

문제에서 요구하는 오름차순 정렬을 먼저 구현한 뒤, 반대로 내림차순으로 정렬하는 알고리즘으로 다시 구현해보았습니다.

감사합니다!!!🍉🍉🍉