계수정렬

[백준] 10989 - 수 정렬하기 3 (자바/Java) : 계수 정렬(Counting Sort)

문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 계수 정렬을 이용하는 문제이다. 처음에 입력 범위가 10,000인 걸 모르고 에러 남..하하 package BOJ0726; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.O..

[백준] 1427 - 소트인사이드 (자바/Java) : 계수 정렬(Counting Sort)

문제 배열을 정렬하는 것은 쉽다. 수가 주어지면, 그 수의 각 자리수를 내림차순으로 정렬해보자. 입력 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 자리수를 내림차순으로 정렬한 수를 출력한다. 자리수를 내림차순으로 정렬한다고 해서 계수 정렬(Counting Sort)가 생각 났다 계수 정렬은 O(N)의 시간 복잡도를 가지는 매우 빠른 정렬으로, 입력되는 숫자들의 범위가 작을수록 사용하기 좋다. 이 문제는 각 자리수를 정렬하는 것이니 0~9까지만 정렬하면 되기 때문에, 계수 정렬을 사용하여 빠른 정렬이 가능하다. 숫자를 String으로 입력 받아, charAt(i)를 이용하여 각 자리수를 int로 바꾸어 주었다. 그리고 0~9까지의..