[伯俊]BOJ 10989 Counting Sort JAVA


配列BOJ 10989数量3

質問する


N個の数字が与えられた場合、昇順で並べ替えられたプログラムを作成します.

入力


第1行は、数の個数N(1≦N≦1000000)を与える.2行目から、N行の数字をあげます.この数は10000以下の自然数です.

しゅつりょく


1行目からN行目まで昇順に並べた結果、1行ずつ出力されます.

サンプルI/O



ソースコード

import java.io.*;

public class Main {
    private static final int MAX = 10_001;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());

        int[] arr = new int[MAX];

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

        for (int i = 1; i < MAX; i++) {
            while(arr[i] > 0){
                sb.append(i).append('\n');
                arr[i]--;
            }
        }
        System.out.println(sb.toString());
    }
}

Comment


  • 条件を満たす方法、カウントソート!インデックスとインデックスに対応する値を使用して、カウントソートを使用します.
  • 2BOJ 2751数量ソート2は、このカウンタを使用してソートすることもできます.でもCollections.sort(Object)StringBuilder()で楽に解けるでしょう.