Counting

[알고리즘] 카운팅 정렬(Counting Sort) (자바/Java)

목차 카운팅 정렬 데이터끼리 비교 없이 데이터의 개수를 세어 정렬하는 알고리즘 제한 정수나 정수로 표현할 수 있는 자료에 대해서만 한정 데이터의 입력 범위가 제한적인 경우에 효율적 데이터의 수는 적지만, 데이터 값의 범위가 큰 경우(ex. 1~10억) count 배열이 메모리를 과다하게 사용하여 비효율적! 시간복잡도 O(n+k) n: 배열의 길이 k: 정수의 최대값 과정 정렬할 배열에서 가장 큰 정수를 크기로 하는 count 배열을 선언한다.. 데이터 값이 i인 경우, count[i]를 1씩 증가시킨다. count가 모두 끝나면, 앞에서부터 누적합하여 count배열을 수정한다. 기존 배열의 맨 마지막 index부터 정렬을 시작한다. arr[n-1]이 k일 경우, count[k]의 값을 찾아, 그 값을 1..

[백준] 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..