정렬 문제를 풀다보면은 ‘입력받는 N의 개수는 많은데’ ‘값의 범위가 작을경우’가 있는데
이때는 Counting Sort(계수 정렬)을 사용하면 보다 쉽게 해결할 수 있음
입력의 개수가 아닌 크기에 영향을 받으므로 최대값의 크기가 큰 경우 매우 비효율적
시간복잡도: O(n)
과정:
1.
입력데이터로 들어올 수 있는 값 중 최대값+1의 크기의 Count Array 배열 생성
2.
입력데이터의 값이 그 값을 저장할 Count Array의 인덱스가 된다 ex) 입력데이터가 2인 경우 Count Array[2] += 1;
3.
데이터들을 다 입력 받았다면, 오름차순일 경우 Count Array의 0인덱스부터 값이 0이 아닌경우에만 출력
4.
내림차순일 경우 마지막 인덱스부터 값이 0이 아닌경우 출력
예제 - 백준 10989
입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
→ 입력 N의 개수는 10,000,000으로 많고 값의 범위는 10,000으로 작은 자연수
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class BOJ10989 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int num = Integer.parseInt(br.readLine());
int[] arr = new int[10001]; // Count Array 생성
for(int i=0; i<num; i++) {
int su = Integer.parseInt(br.readLine());
arr[su] +=1;
}
// arr의 배열의 0 인덱스부터
for(int i=0; i<arr.length; i++) {
//값이 0이 아니면
if(arr[i]!=0) {
// 값의 크기만큼 출력해준다
for(int j=0; j<arr[i]; j++) {
sb.append(i).append("\n");
}
}
}
System.out.println(sb.toString());
}
}
JavaScript
복사
입력
10
5
2
3
1
4
2
3
5
1
7
JavaScript
복사
출력
1
1
2
2
3
3
4
5
5
7
JavaScript
복사
