[알고리즘] 백준 10989번 "수 정렬하기 3" (C/C++) - Don 임베디드

문제요약:

N개의 수 A[1] A[2] A[3] ... A[N] 이 주어진다. 

이를 오름차순으로 정렬하여 출력하는 프로그램을 작성하라.

(Counting Sort/ 계수 정렬을 사용하여 정렬하라.)

 

제약:

시간 제한 5초, 메모리 8MB

1 <= N <= 10,000,000

1 <= A[i] <= 10,000

N과 A[i]는 자연수.

 

 

예제 1 입력.	예제 1 출력.
10 5 2 3 1 4 2 3 5 1 7	1 1 2 2 3 3 4 5 5 7

 

 

정답코드:

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <memory.h>
 
#define MAX_NUM_VALUE (10001)
 
using namespace std;
 
int anCount[MAX_NUM_VALUE];
 
int main()
{
    register int N, nCurrentNum, nTmp;
    register int nMax = -1;
 
    scanf("%d", &N);
 
    // Initialize anCount
    memset(anCount, 0, MAX_NUM_VALUE * sizeof(int));
 
    for (register int j = 1; j <= N; j++)
    {
        scanf("%d", &nCurrentNum);
 
        // Update Max Number
        if (nMax < nCurrentNum)
        {
            nMax = nCurrentNum;
        }
        anCount[nCurrentNum]++;
    }
 
    // print out sorted Numbers
    for (register int k = 1; k <= nMax; k++)
    {
        if (anCount[k] == 0)
        {
            continue;
        }
        else
        {
            nTmp = anCount[k];
            while (nTmp-- > 0)
            {
                printf("%d\n", k);
            }
        }
    }
 
    return 0;
}

 

원본 링크: https://www.acmicpc.net/problem/10989

 

추가)

Counting Sort를 반드시 사용하게 하기 위해서 시간이 빡빡하게 주어집니다.

저도 몇 번을 시간 초과로 실패했는데,

cin, cout 사용하지 않고 scanf, printf를 사용하니 통과하네요.

memset, register는 cin, cout 사용하면서 시간 초과에 고통받았던 흔적입니다.ㅎㅎ