[백준 10989번] [Java] 수 정렬하기 3

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

10989번: 수 정렬하기 3

 

난이도 : 브론즈 1
태그 : 정렬

 

 

설명

중복되는 수가 주어지는 상황에서의 정렬입니다.

 

수의 개수가 1부터 10,000,000개로 매우 많습니다.

하지만 n의 범위는 1부터 10,000으로 그리 많지는 않습니다.

 

n의 개수와 범위를 봤을 때, 이 문제에서는 카운팅 정렬(계수 정렬)을 쓰면 좋을 것 같습니다.

 

계수 정렬

계수 정렬은 1~n 길이의 배열을 만들어놓고,

특정 데이터가 들어올때마다 해당 인덱스의 값을 +1 해주는 방식의 정렬입니다.

 

예시와 함께 보고 가시죠.

n의 범위가 1~5라고 가정하고,

4, 5, 2, 3, 4, 2 이렇게 6개의 데이터를 정렬해보겠습니다.

각 원소를 카운팅할 배열이 하나 필요하겠네요.

int arr[] = new int[6]; 를 하나 만듭니다. 0번째는 사용하지 않습니다.

 

첫 번째 데이터 4가 들어왔네요. 4번째 값을 +1 해봅시다.

남은 원소 : 5, 2, 3, 4, 2

arr : { 0, 0, 0, 0, 1, 0 }

 

두번째로  5 입니다. 배열의 5번째 원소를 +1 합니다.

남은 원소 : 2, 3, 4, 2

arr : { 0, 0, 0, 0, 1, 1}

 

세번째로 2 입니다. 배열의 2번째 원소를 +1 합니다.

남은 원소 : 3, 4, 2

arr : { 0, 0, 1, 0, 1, 1 }

 

위 과정을 반복해봅시다.

 

남은 원소 : 4, 2

arr : { 0, 0, 1, 1, 1, 1 }

 

남은 원소 : 2

arr : { 0, 0, 1, 1, 2, 1 }

 

남은 원소 : 없음

arr : { 0, 0, 2, 1, 2, 1 }

 

이를 1번째부터 5번째 원소까지 개수만큼 출력하면 됩니다.

2 2 3 4 4 5 가 되겠네요.

 

카운팅 정렬(계수 정렬) 이라는 알고리즘 이름처럼 카운팅 하는 방식으로 작동됩니다.

 

 

소스코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int inputCase = Integer.parseInt(br.readLine());
        int[] arr = new int[10001];
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < inputCase; i++) {
            arr[Integer.parseInt(br.readLine())]++;
        }

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

        System.out.println(sb);
    }
}

 

위의 방법을 소스코드로 옮긴 것입니다.

 

 

후기

계수정렬은 배울때 이런 식으로 정렬할 수도 있구나, 하면서 꽤 신기했던 기억이 납니다.

데이터의 개수가 많되, 범위가 적을수록 효과적입니다.

단, 배열을 사용하는 만큼 데이터들이 정수일때를 전제로 합니다.