Baekjoon Online Judge

algorithm practice

단계별 문제풀기

12. 정렬

배열의 원소를 순서대로 나열하는 알고리즘을 배워 봅시다.

Java / Python

3. 수 정렬하기3

10989번

수의 범위가 작다면 카운팅 정렬을 사용하여 더욱 빠르게 정렬할 수 있습니다

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

카운팅 정렬(Counting Sort)이란?

항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적인 알고리즘입니다.

• 보통 정렬할 값이 양의 정수이고, 자료의 범위를 알고 있을 때 사용한다고 합니다.
• 정수나 정수로 표현할 수 있는 자료에 대해서만 적용이 가능하고, 각 항목의 발생 횟수를 기록하기 위해, 정수 항목으로 인덱스 되는 카운트들의 배열을 사용합니다.
• 카운트들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야 합니다.
• 시간 복잡도는 O(n+k)입니다.
  여기서 n은 정렬할 리스트의 길이이며, k는 리스트의 정수 최댓값을 의미합니다.
  그래서 C의 크기가 충분히 작을 때는 O(n)의 복잡도를 가지겠지만, k가 커질 경우 O(n+k)의 복잡도를 가집니다. (즉, 입력데이터의 최댓값인 k가 커질수록 시간 복잡도가 커진다고 볼 수 있습니다.)

• Java
  
  

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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())] ++;// 해당하는 인덱스 값 1 증가
        }
        br.close();
        StringBuilder sb = new StringBuilder();
        // 0은 입력범위에서 제외 / 1부터 시작
        for(int i = 1; i < 10001; i++){
        // i 값이 개수가 0 이 될 때 까지 출력 (= 빈도수)
            while(cnt[i] > 0){
                sb.append(i).append('\n');
                cnt[i]--;
            }
        }
        System.out.println(sb);
    }
}

수의 범위 (0 ~ 10000)
cnt 크기 10001로 선언

• Python

import sys 

N = int(input()) 
check_list = [0] * 10001 

for i in range(N): 
    num = int(sys.stdin.readline()) 
    check_list[num] = check_list[num] + 1 
    
for i in range(10001): 
    if check_list[i] != 0: 
        for j in range(check_list[i]): 
            print(i)

input()함수보다 빠른 sys 라이브러리에 있는 sys.stdin.readline()을 사용했습니다.