[백준]10989번: 수 정렬하기 3 [C#]

첫째 줄에 반복 횟수가, 둘째 줄부터 정렬할 정수가 한줄 씩 입력된다.

입력 횟수 자체는 10,000,000회로 무척 많지만, 입력되는 수는 최대 10,000 이므로 10,000칸의 배열을 만들고, 해당 배열을 한 칸씩 이동하며 0이 아닐때 1식 차감하며 해당 인덱스의 번호를 뱉는 식으로 짜면 될 것 같다.

using System.Text;
 
namespace 연습장
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            int[] Arr = new int[10001];
 
            for (int i = 0; i < N; i++)
            {
                int input = int.Parse(Console.ReadLine());
                Arr[input]++;
            }
 
            for (int j = 1; j < Arr.Length; j++)
            {
                while (Arr[j] != 0)
                {
                    Arr[j]--;
                    Console.WriteLine(j);
                }
            }
        }
    }
}
 

코드는 얼추 맞게 작성한 거 같은데 시간 초과라고 뜬다.

입력이 최대 10,000,000회 까지 주어지다 보니 그런 것 같다. 더 줄일 방법을 찾아야겠다.

 

using System.IO;
using System.Text;
 
namespace 연습장
{
    internal class Program
    {
        static void Main(string[] args)
        {
            StringBuilder sb = new StringBuilder();
            int N = int.Parse(Console.ReadLine());
            int[] Arr = new int[10001];
 
            for (int i = 0; i < N; i++)
            {
                int input = int.Parse(Console.ReadLine());
                Arr[input]++;
            }
 
            for (int j = 1; j < Arr.Length; j++)
            {
                while (Arr[j] != 0)
                {
                    Arr[j]--;
                    sb.Append(j + "\n");
                }
            }
            Console.WriteLine(sb);
        }
    }
}

빠른 출력을 위해 오늘 배웠던 StringBuilder를 이용해 출력을 해보았는데, 용량이 초과되었다.

입력이 너무 커서 이 방법도 별로인 것 같다.

using System.IO;
using System.Text;
 
namespace 연습장
{
    internal class Program
    {
        static void Main(string[] args)
        {
            using var reader = new StreamReader(Console.OpenStandardInput());
            using var print = new StreamWriter(Console.OpenStandardOutput());
            int N = int.Parse(reader.ReadLine());
            int[] Arr = new int[10001];
 
            for (int i = 0; i < N; i++)
            {
                Arr[int.Parse(reader.ReadLine())]++;
            }
 
            for (int j = 1; j < Arr.Length; j++)
            {
                while (Arr[j] != 0)
                {
                    Arr[j]--;
                    print.WriteLine(j);
                }
            }
        }
    }
}
 

찾아보니 입출력 속도를 높히는 방법이 몇개 더 있었다. 그 중 하나다 Stream(Reader/Writer)인데,

이 친구들은 특정한 스트림(데이터의 흐름을 추상화 한 것) 을 읽거나 쓴다.

또 OpenStandard(Input/Output)은 바이트 스트림을 열어서 프로그램으로 스트림이 들어오거나 나가게 해준다고 한다.

평소에 쓰던 ReadLine()과 WriteLine() 모두 이 OpenStandard(Input/Output)을 내장하고 있다고 한다.