C# 백준 문제 번호 10989 - 수 정렬하기 3

문제

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

입력

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

출력

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

 

이 문제는 입력받는 수의 개수 N과 메모리 제한이 핵심인 듯하다

 

처음엔 입력받은 수를 배열에 다 저장한 후에 정렬을 시도했는데 

 

최대 10,000,000 개의 수를 입력받으니 당연하게도 메모리 제한에 걸렸고

 

입력받는 최대 숫자가 10,000인 거에 힌트를 얻어서 따로 정렬하지 않고 출력하였다.

using System;
using System.Collections.Generic;
using System.Text; 
class Program
{
    static void Main(string[] args)
    {
            //입력 받을 수의 갯수
            int N = int.Parse(Console.ReadLine());
 
            int MAX_NUM = 10000; //입력 받는 수의 최대 값
            int[] countArray = new int[MAX_NUM + 1]; //입력 받은 수 카운트 할 배열
 
             //입력 받은 수를 카운팅
            int temp = 0;
            for(int i = 0; i < N; i++)
            {
                temp = int.Parse(Console.ReadLine());
                countArray[temp]++;
            }
 
           using (var print = new System.IO.StreamWriter(Console.OpenStandardOutput()))
           {
             //카운팅 된 숫자를 출력
             for(int i = 0; i <= MAX_NUM; i++)
             {
                if (countArray[i] == 0) continue;
 
                for(int j = 0; j < countArray[i]; j++)
                {
                    print.WriteLine(i);
                }          
             }
           }
 
    }
}

 

배열 문제를 해결하고도 메모리 제한, 시간 초과로 계속 실패했는데 

 

출력 방식이 문제였다. 보통은 StringBuilder를 사용하면 거의 해결이 되었는데 이번 경우엔 그것 조차 안되어서 

 

C#으로 가능한가? 싶었지만 방법은 있었다. 위의 소스처럼 StreamWriter를 사용하면 해결이 가능하다.

 

참고한 출력 속도 비교 자료 

https://www.acmicpc.net/blog/view/57

출력 속도 비교

 

 

10989 문제 링크

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

10989번: 수 정렬하기 3