[10989] 수 정렬하기3(C#)

10,000보다 작거나 같은 수를 최대 천만번 input을 받아서 정렬하는 문제로

Sorting과 관련한 내장함수로는 통과 조건을 만족할 수 없다.

천만번 input을 받는 대신에 그 값의 범위가 좁은 편이기 때문에

이럴때는 계수정렬 알고리즘을 활용한다.

 

계수정렬(Counting Sort)?
배열의 인덱스를 특정한 데이터의 값으로 여기는 정렬 방법
배열의 크기는 데이터의 범위를 포함할 수 있도록 설정하고 각 배열의 값으로는 데이터가 등장한 횟수를 세어 입력
시간복잡도 : O(N)

int N = int.Parse(Console.ReadLine());
int[] arrInt = new int[10001];

for (int i = 0; i < N; i++)
{
    int intThisInput = int.Parse(Console.ReadLine());
    arrInt[intThisInput] += 1;
}

for (int i = 0; i < arrInt.Length; i++)
{
    if (arrInt[i] == 0)
        continue;
    for (int j = 0; j < arrInt[i]; j++)
        Console.WriteLine(i);
    
    // 아래와 같이 Enumerable.Repeat(count, string) 수행 시 
    // string을 count만큼 반복하는 IEnumerable<T out>을 return한다.
    // Console.WriteLine(String.Join("\n", Enumerable.Repeat(i, arrInt[i]).ToArray()));
}

Enumerable 적용 시 메모리초과 에러..

단순 for문 수행 시 시간초과 에러...

그래서 결론은 아직 완전한 해답을 모른다ㅠㅠ