[알고리즘 / 백준] 10989 - 수 정렬하기 3

 

문제는 위와 같으며 이 문제의 경우 계수 정렬 알고리즘을 사용하여 해결할 수 있습니다.

 

계수 정렬(Counting Sort) 알고리즘을 간략하게 살펴보면 배열의 인덱스 값을 특정한 데이터의 값으로 여기는 정렬 방법입니다. 배열의 크기는 데이터를 포함할 수 있도록 설정하고 해당 인덱스의 수가 등장한 횟수를 세는 방식입니다. 이 알고리즘은 주어지는 수는 많지만 수의 범위가 제한적일 때 효율적으로 사용할 수 있습니다. 

 

파이썬 코드를 보면 다음과 같습니다.

from sys import stdin

n = int(stdin.readline())
nums = [0 for _ in range(10001)]  # 배열의 크기는 10001 이고, 0으로 초기화 => [0] * 10001 로 써도 됨

for _ in range(n):
    num = int(stdin.readline())
    nums[num] += 1  # 주어진 수가 index 인 값을 counting

for i in range(len(nums)):
    for _ in range(nums[i]):
        print(i)

 

자바 코드를 보면 다음과 같습니다. 자바의 경우는 출력 시 System.out.println() 을 반복적으로 사용할 경우 시간 초과가 발생하여 StringBuilder 를 이용해 출력할 데이터를 모두 담은 뒤 한번에 출력하는 방식을 사용하였습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        int[] nums = new int[10001];

        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(br.readLine());
            nums[num] += 1;
        }

        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums[i]; j++) {
                sb.append(i).append("\n");
            }
        }

        System.out.println(sb);
    }
}