백준 11단계 no.3

계수 정렬 참고 : https://st-lab.tistory.com/104

자바 [JAVA] - 카운팅 정렬 (Counting Sort / 계수 정렬)

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

public class Main {
    static int max (int[] arr) {
        int max = arr[0];
        for (int j : arr) {
            if (j >= max) {
                max = j;
            }
        }
        return max;
    }

    static int min (int[] arr) {
        int min = arr[0];
        for (int j : arr) {
            if (j <= min) {
                min = j;
            }
        }
        return min;
    }

    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 = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        int[] result = new int[n];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        int max = max(arr);
        int min = min(arr);

        int[] count = new int[max-min+1];
        for (int i = 0; i < arr.length; i++) {
            count[arr[i]-min]++;
        }

        for (int i = 1; i < count.length; i++) {
            count[i] = count[i] + count[i-1];
        }

        for (int i = arr.length-1; i > -1; i--) {
            result[count[arr[i]-min]-1] = arr[i];
            count[arr[i]-min]--;
        }

        for (int j : result) {
            bw.write(j + "\n");
        }
        bw.flush();
        bw.close();
    }
}