[10989] 수 정렬하기 3

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

입력

• 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

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

생각

입력에 대한 시간제한이 있기 때문에, 문제에서 제시한 대로 카운팅정렬을 사용해야 한다.
출력 또한 StringBuilder가 필수다.

참고

처음 코드

using System.Text;

namespace SongE
{
    public class Program
    {
        static int[] CountSort(int[] list, int n)
        {
            int[] cnt = new int[10001];
            int[] ans = new int[10001];

            for (int i = 0; i < n; i++) cnt[list[i]]++;
            for (int i = 1; i <= 10000; i++) cnt[i] += cnt[i - 1];

            for(int i = n-1; i >= 0; i--)
            {
                int target = list[i];
                ans[cnt[target] - 1] = target;
                cnt[target]--;
            }

            return ans;
        }
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int[] nums = new int[n];
            for(int i = 0; i < n; i++)
            {
                nums[i] = int.Parse(Console.ReadLine());
            }
            int[] ans = CountSort(nums, n);

            StringBuilder sb = new StringBuilder();
            for(int i = 0; i < n; i++) sb.AppendLine($"{ans[i]}");

            Console.WriteLine(sb.ToString());


        }
    }
}

메모리 초과가 뜸.

그 뒤로 배열을 short로 바꾸고 하는 여러번의 시도를 했으나 메모리초과.
찾아보니 ReadLine의 시간과 StringBuilder도 문제라고 한다.

그래서 StreamReader, StreamWriter을 채용하였고
기존 코드에서는 배열이 많아서 그런지 계속 메모리 초과가 떠서
최대한 줄였다. 그냥 함수도 없앰 ㅎㅎ;

참고

입력 받은 수를 인덱스로 하여 해당 인덱스의 배열값을 1씩 추가해준 뒤,
끝나고 나서 해당 배열의 인덱스에 있는 수만큼 인덱스를 출력해주면
차례대로 출력된다.

코드

using System;
namespace SongE
{
    public class Program
    {
        static void Main(string[] args)
        {
            using var reader = new System.IO.StreamReader(Console.OpenStandardInput());
            using var print = new System.IO.StreamWriter(Console.OpenStandardOutput());
            
            int n = int.Parse(reader.ReadLine());

            int[] nums = new int[10001];

            for(int i = 0; i < n; i++)
            {
                nums[int.Parse(reader.ReadLine())]++;
            }
            for(int i = 0; i <= 10000; i++)
            {
                if (nums[i] != 0)
                {
                    for(int j = 0; j < nums[i]; j++)
                    {
                        print.WriteLine(i);
                    }
                }
            }

        }
    }
}