백준 10989 수 정렬하기 3

문제

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

---

코드

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

class Main {
    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[] counting=new int[20000001];
        int[] array=new int[n];
        int[] sorted=new int[n];

        for(int i=0; i<n; i++)
            array[i]=Integer.parseInt(br.readLine());
        for(int i=0; i<n; i++)
            counting[array[i]]++;
        for(int i=0;i<20000000;i++)
            counting[i+1]+=counting[i];
        for(int i=n-1; i>=0; i--)
            sorted[--counting[array[i]]]=array[i];
        for(int i:sorted)
            bw.write(i+"\n");

        bw.flush();
    }
}

---

해결 과정

1. 최대 1000만 개의 수가 주어지지만 수의 범위가 1~10000 으로 매우 작아서 Counting Sort로 정렬했다.
2. 😁