[BackJoon]10989번

문제

 

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

 

입력

 

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 

둘째 줄부터 N개의 줄에는 수가 주어진다.

이 수는 10,000보다 작거나 같은 자연수이다.

 

출력

 

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

 

풀이

 

카운팅 정렬은 대상 배열의 크기 N과 원소중 최댓값 k에 따라 O(N + k)의 시간 복잡도를 가진다.

 

이는 배열의 크기가 작고, 수의 범위가 좁을수록 무시무시한 속도를 자랑하는데,

 

이번 문제는 그 카운팅 정렬을 구현해보라는 문제이다.

 

다른 글에서 구현했으므로, 여기서는 그냥 가져다 쓴다.

 

2022.12.27 - [Development/Java] - [Algorithm]카운팅 정렬(Counting Sort)

[Algorithm]카운팅 정렬(Counting Sort)

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

public class Prob10989 {

    private static int[] result;

    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[] target = new int[n];

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

        countingSortImpl(target);

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

    public static void countingSortImpl(int[] target) {

        int[] counting = new int[Arrays.stream(target).max().getAsInt() + 1];
        result = new int[target.length];

        for (int i = 0; i < target.length; i++) { // Counting
            counting[target[i]]++;
        }

        for (int i = 1; i < counting.length; i++) { // 누적 합
            counting[i] += counting[i - 1];
        }

        for (int i = target.length - 1; i >= 0; i--) { // 정렬
            counting[target[i]]--; // 해당 인덱스 값을 하나 줄여주고
            result[counting[target[i]]] = target[i]; // 줄여진 수를 인덱스 삼아 result에 값 채우기
        }
    }
}