[자료구조] Counting Sort

 

Counting Sort

• 각 수의 등장 횟수를 세아려 정렬하는 방법
  • 배열의 인덱스를 수로 하고, 배열[인덱스]를 수의 등장 횟수로 한다. 
  • 배열의 인덱스가 작은 순서부터 배열[인덱스]를 등장 횟수만큼 출력한다.  
• 수의 범위가 한정적일 때만 사용가능
  • 시간복잡도가 O(N+K)이다. K(수의 범위)가 크면 시간초과가 난다. 

 

 

BOJ 15688 - 수 정렬하기 5 

 

문제

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

길이가 K인 수열 A가 A1 <= A2 <= ... <= Ak-1 <= Ak를 만족하면, 비내림차순이라고 한다. 

 

 

입력

첫째 줄에 수의 개수 N(1 <= N <= 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 

이 수의 절댓값이 1,000,000보다 작거나 같은 정수이며, 같은 수가 여러 번 중복될 수 있다. 

 

 

출력

첫째 줄부터 N개의 줄에 비내림차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 

 

 

예제 입력1

5
5
4
3
2
1

 

예제 출력1

1
2
3
4
5

 

 

예제 입력2

5
1
2
1
2
1

 

예제 출력2

1
1
1
2
2

 

 

풀이

정렬할 숫자의 범위는 절댓값이 1,000,000보다 작거나 같은 정수이다. 

범위는 -1,000,000 <= 숫자 <= 1,000,000 가 되겠다. 

 

-1,000,000은 음수라서 인덱스로 사용할 수 없다. 

-1,000,000의 등장횟수를 배열에 저장하는 방법은 -1,000,000을 0번째 인덱스로 하는 것이다. 

-1,000,000 + 1,000,000 = 0. 0번째 인덱스를 -1,000,000번 숫자로 하고, 1,000,000는 1,000,000 + 1,000,000번째 인덱스로 설정하면 된다. 

 

시간복잡도를 생각해보면

배열에 N개의 수를 저장하고, 답을 출력할때 K(수의 범위)칸을 출력해야 한다. 

따라서 시간복잡도는 O(N+K)

 

K가 작으면 Counting Sort가 효율적이며, K가 크면 Counting Sort는 사용할 수 없다. 

 

 

코드

using System.Text;

namespace 정렬
{
    internal class BOJ15688_수_정렬하기5
    {
        static StreamReader sr = new StreamReader(Console.OpenStandardInput());
        static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
        static StringBuilder sb = new StringBuilder();

        static int[] freq = new int[2000001];

        static void Main(string[] args)
        {
            int N = int.Parse(sr.ReadLine());

            for(int i = 0; i < N; i++)
            {
                int index = int.Parse(sr.ReadLine());
                freq[index + 1000000]++;
            }

            for(int i = 0; i <= 2000000; i++)
            {
                while (true)
                {
                    if (freq[i] == 0) break;
                    sb.Append($"{i - 1000000}\n");
                    freq[i]--;
                }
            }

            sw.WriteLine(sb.ToString());

            sr.Close();
            sw.Close();
            sb.Clear();
        }
    }
}