기수 정렬을 이용한 문제 풀이 - 수 정렬하기

* Do it 코딩테스트 책을 참고하였습니다. - 백준 온라인 저지 10989번 문제

 

 해당 문제는 10000보다 작거나 같은 자연수들의 배열을 오름차순으로 정렬하는 문제이다. 줄의 개수가 광범위하기 때문에 단순하게 정렬을 하기 위해서 sort() 메소드를 사용하거나 효율이 좋지 않은 정렬법을 사용하게 되면 시간 초과로 인해서 제한시간안에 값을 구해내지 못하게 된다.

 

 그렇기 때문에 해당 문제를 풀기 위해서는 값들을 어떤 정렬을 이용하여야 효율적으로 풀 수 있는지 알아내는 것이 중요하다. 문제에서 주어지는 수들은 앞서 말한 것과 같이, 10000보다 작거나 같은 자연수들이다. 그렇기 때문에 1부터 10000까지 각 숫자가 몇개 있었는가? 라는 아이디어를 통해서 풀 수 있다. 해당 개념이 바로 기수 정렬이다. 기수 정렬은 O(kn)이라는 시간복잡도를 지닌다. 여기서 k는 숫자의 자릿수를 의미한다. 그렇기 때문에 숫자들의 자릿수가 적어지는 만큼 기수 정렬의 효율은 좋다고 할 수있다. 이번 문제는 값의 범위가 작기 때문에 해당 문제를 푸는데에 기수 정렬은 탁원한 선택이라고 할 수있다. 

 

 기수 정렬은 일의 자릿수부터 시작하여 가장 큰 수의 자릿수까지 정렬을 해 나아가며 정렬을 하는 방법이다. 이 방법에 대한 자세한 방법에 대해서는 기회가 된다면 따로 알고리즘 파트에 글을 작성할 예정이다.

 

 코드를 보면서 확인해보겠습니다.

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;
    int count[10001] = { 0 };
    int number = 0;

    for (int i = 0; i < N; i++)
    {
        cin >> number;
        count[number]++;
    }

    for (int i= 0; i <= 10000; i++)
    {
        if (count[i] != 0) 
        {
            for (int j = 0; j < count[i]; j++)
                cout << i  << endl;
        }
    }
	return 0;    
}

 1부터 10000까지의 모든 숫자에 대해서 입력값에 따라 해당 숫자를 인덱스로 가지는 배열의 원소를 1씩 더해주어 결과적으로 각 숫자가 입력으로 몇 개가 들어왔는지 체크 후, 해당 원소의 값만큼 출력을 해주면서 최종적으로 오름차순으로 정렬된 값의 형태를 가질 수 있게 되는 것이다.

 

 이것으로 수 정렬하기 문제에 대한 풀이를 마치도록 하겠습니다. 포바~!