[規格10999]カウントソート(正解率23%)
1477 ワード
解き方
3-1. カウントソートは時間複雑度O(n)を適用し,場合によっては最も速い性能を示す.
3-2. 場合によっては、整数の個数は重要ではなく、範囲が重要であるほど(範囲が大きいほど効率が低下する)
3-3.
import java.io.*;
public class Main {
private static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
private static BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
int[] counter = new int[10001];
int inputCount = Integer.parseInt(bufferedReader.readLine());
while (inputCount-- > 0) {
int inputNum = Integer.parseInt(bufferedReader.readLine());
counter[inputNum]++;
}
for (int i = 0; i < 10001; i++) {
while (counter[i] > 0) {
bufferedWriter.append(i + "\n");
counter[i]--;
}
}
bufferedWriter.flush();
}
}
他人の答え
ソート条件が非常に厳しいため、すべての使用カウントソート
に感銘を与える
整数の個数や範囲が大きい場合は、マージソート、hipソートなどが望ましい.
範囲が小さいほど、カウントソートが有効になります.
ex)アルファベットソート等
Reference
この問題について([規格10999]カウントソート(正解率23%)), 我々は、より多くの情報をここで見つけました https://velog.io/@kw78999/백준10989-카운팅-정렬정답률-23テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol