[백준] 10989 : 수 정렬하기 3 (Counting sort) - JAVA

백준 단계별 문제풀이 13단계 (정렬)

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

 

 

# 문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

 

# 예제

입력 : 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수

10
5
2
3
1
4
2
3
5
1
7

 

출력

1
1
2
2
3
3
4
5
5
7

 

# 필요개념

이 문제는 시간 제한 3초와 메모리 제한 512MB가 있다. 그래서 메모리가 큰 Collections.sort()를 사용할 수 없다!

Arrays.sort()와 BufferedReader로 풀리긴 하나 간당간당한 느낌이 있어 다른 풀이방법을 이용했다.

 

 

카운팅 정렬 (Counting sort)

계수정렬이라고 불리는 카운팅 정렬은 시간복잡도가 O(n)으로 성능이 아주 좋은 알고리즘이다. 알고리즘 시간에 sorting 알고리즘은 O(nlogn)이 한계라고 배웠는데 어떻게 이런 시간복잡도가 나오는 것일까 ?

힙정렬, 퀵정렬, 병합정렬처럼 데이터끼리 직접 비교하는 알고리즘은 O(nlogn)이 한계가 맞다 ! 그럼 카운팅 정렬은 어떤 원리로 돌아가는 것일까 ?

 

카운팅정렬의 기본 매커니즘은 데이터의 값이 몇 번 나왔는지 세는 것이라고 한다. 과정은 다음과 같다.

 

1.  Array를 한 번 돌면서 나오는 값을 인덱스로 하는 새 배열을 만들고, 그 값을 1씩 증가시킨다. 예를 들면 
   array = {7, 2, 3, 5, 7, 1, 4}가 있다면 새 배열 count는 array[0] = 7 이므로 count[7] += 1이 된다. 이 과정을 거치면 count
   배열은 다음과 같이 값이 매겨진다. count = {0,1,1,1,1,1,0,2}
   
   
2. count배열의 각 값을 누적합으로 변환한다. 누적합은 인덱스 i와 i+1을 더해 i+1 자리에 넣는 것이다.
   count[0] = 0, count[1] = 0 + 1 = 1, count[2] = 1 + 1 = 2 ... 이므로 count = {0, 1, 2, 3, 4, 5, 5, 7} 이 된다.
   
   
3. array의 뒤에서부터 순회하며 array의 값을 인덱스로 갖는 count를 찾아 1을 줄이고, count값을 인덱스로 갖는 새로운 배열 result를 만들어 count의 인덱스값을 값으로 갖게 한다.

출처 - https://st-lab.tistory.com/104#recentEntries

 

이 과정을 array 인덱스가 0이 될 때까지 반복해 result 배열을 만들어준다. 그러나 array값의 범위에 따라 counting 배열의 길이가 달라지므로 메모리 낭비가 일어날 수 있다.

 

# Code

import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
    
        int[] cnt = new int[10001];
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
 
        for (int i = 0; i < N; i++) {
            cnt[Integer.parseInt(br.readLine())] ++;
        }
 
        br.close();
        StringBuilder sb = new StringBuilder();

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

 

# 결과