[BOJ] 10989번 수 정렬하기 3 C# 사용 못풀이 (해결)

문제

기존 풀이 (메모리 오버가 되어 계속 틀렸다고 나왔다.)

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace BOJ01
{
    class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
            int N = int.Parse(sr.ReadLine());

            int[] list = new int[N];   
            
            for (int i = 0; i < N; i++)
            {
                list[i] = int.Parse(sr.ReadLine());    
            }

            var list2 = from num in list
                        orderby num
                        select num;


            foreach (int i in list2) { sw.WriteLine(i); }


            sr.Close();
            sw.Flush();
            sw.Close();
        }
    }
}

완료하지 못한 알고리즘 흑흑 

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace BOJ01
{
    class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
            int N = int.Parse(sr.ReadLine());
            int[] list = new int[N]; 
            int[] list2 = new int[10000];
            int index = 0;
          
            for(int i = 0; i < N;i++) 
            {                
                index = list[i] = int.Parse(sr.ReadLine());
                if (list2.Contains(list[i]))
                {
                     
                }
                else
                list2[index] = list[i];   
            }
            index = 0;
            for(int i = 0; i<10001; i++) 
            {               
                if (list2[i] != 0)
                {                  
                    if (list2[i] == index)
                        sw.WriteLine(i);                   
                }
                index++;
            }
            sr.Close();
            sw.Flush();
            sw.Close();
        }
    }
}

이었지만 Counting sort 를 어떻게 이용해야 하는지 알아냈다.

 

요약하자면 받은 모든 숫자를 정렬하면 시간 초과가 뜨기 때문에 입력되는 값이 10000보다 작은 걸 이용하여 10000개의 인덱스에 10000개의 0을 가지고 있는 배열을 생성하여 입력되는 숫자와 같은 정수 배열의 인덱스 요소값을 입력될때 마다 +1 해주고 그 이후에 해당 인덱스 요소값이 0이 아닌 숫자들을 차례대로 출력해주면 되는 문제였다. (이를 위해 이중포문을 돌며 중복 숫자들 또한 처리하였다.

 

풀이

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace BOJ01
{
    class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            int N = int.Parse(sr.ReadLine());  // 최대 입력받을 숫자
            int[] ints = new int[10001];       // 10000개의 요소를 가지는 배열 (0부터 for 문을 돌리니 10001 로 지정)
            
                
            for (int i = 0; i < N; i++)             //for문을 돌며 해당 입력받은 숫자와 같은 인덱스의 요소값을 +1
            {
                int num = int.Parse(sr.ReadLine());
                ints[num]++;  
            }

            for(int i = 0; i < 10001; ++i)  // 변수 i 는 0~10000까지 순회하며 정수 배열 인덱스에 대입, 이후 요소 값이 0이 아닌 인덱스가 있다면..!
            {
                if (ints[i] != 0)   
                for (int j = 0; j <ints[i]; j++)    //해당 인덱스를 출력 , 또한  인덱스의 숫자 = 입력된 중복숫자 이기 때문에 중복 처리 가능
                {                   
                    sw.WriteLine(i);
                }
            }

            sr.Close();
            sw.Flush();
            sw.Close();
        }
    }
}

 

결과창

 

정답!! (채점에 시간이 오래걸려 틀린줄 ㅠ)