BOJ 10989 수 정렬하기 3 [Java]

BOJ 10989 수 정렬하기 3

- 문제 링크

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

- 문제 해설

N이 10,000,000 이하의 자연수이기 때문에 sort를 쓰면 메모리 초과가 난다는 사실을 인지해야한다.
정렬해야하는 숫자들이 10,000 이하라는 사실에서 counting sort를 쓰면 되겠다는 힌트를 얻었다.
cnt[i]를 1-10000 범위의 자연수 i가 입력된 횟수라고 설정하고 구현해주면 된다.
출력할 때는 cnt[i] > 0 이 아닌 경우에는 i가 입력되지 않은 경우이니 제외한다.

- 코드 보기

import java.io.*;

public class Main
{
    static int n;

    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());
        int cnt[] = new int[10005];

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

        for (int i = 1; i <= 10000; i++)
        {
            if (cnt[i] > 0)
            {
                for (int j = 0; j < cnt[i]; j++)
                {
                    bw.write(i + "\n");
                }
            }
        }

        br.close();
        bw.flush();
        bw.close();
    }
}