백준 알고리즘 C# 10989 수 정렬하기 3 - MJ

  문제

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

 

  Code

using System;
namespace PracticeAlgo
{
    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 count = Convert.ToInt32(reader.ReadLine());
            int[] list = new int[10001];
 
            for (int i = 0; i < count; i++)
            {
                list[int.Parse(reader.ReadLine())]++;
            }
            for (int i = 0; i <= 10000; i++)
            {
                if (list[i] != 0)
                {
                    for (int j = 0; j < list[i]; j++)
                    {
                        prnt.WriteLine(i);
                    }
                }
            }
        }
    }
}

 

 

  생각

1. 10,000,000줄을 Read하면 시간이 모자라겠다. 그리고 1~10000까지 모든 숫자가 들어오면 Write하는 것도 힘들겠다.

2. 또한, 메모리도 5MB 제한으로 StringBuilder를 통해 빠르게 Write하는 것이 불가능하다.

3. 크게 2가지 방법이 있을 것이다.

   1) 열심히 받을 때 부터 줄을 세우는 것

      - 하나씩 앞에서부터 비교하여 줄세우기.

      - 이진 탐색을 구현하여 값을 넣을 Index 찾고 줄세우기

     이 List를 Write 한다.

   2) 1~10000을 담을 수 있는 배열을 즉, 공간이 10000개가 되는 배열을 만든다.

       숫자가 들어오면 그 배열의 해당 위치 값을 1씩 증가한다.

       for를 이용하여 배열 안의 값만큼 index를 Write한다.

4. 1) 방법은 메모리 문제와 시간에서 문제가 발생할 것이다. 따라서 2) 방법으로 실행한다.

 

  이론

정렬하기.

StreamReader  와 StreamWriter 를 이용하여 빠르게 읽고 쓴다.

망할 C#이다.... 정말 느리다.

이를 극복하기 위해 C#으로 알고리즘을 풀 때 StreamReader와 StreamWriter를 많이 사용합니다.

또한, StringBuilder를 많이 사용한다.

이에 대한 설명은 추후에 TIP을 통해 정리하여 설명하겠습니다.