[10814] 나이순 정렬

온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.

입력

• 첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000)
  둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다.

출력

• 첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다.

생각

stable해야한다. age가 같다면 입력한 순서대로 안바뀌도록 해주어야 함.

처음 코드

namespace SongE
{
    struct People
    {
        public int age;
        public string name;
    }
    public class Program
    {
        static void Merge(People[] p, int left, int mid, int right)
        {
            int i = left, j = mid + 1, k = left, l;
            People[] temp = new People[p.Length];
            while (i <= mid && j <= right)
            {
                if (p[i].age <= p[j].age)
                    temp[k++] = p[i++];
                else
                    temp[k++] = p[j++];
            }
            
            if(i>mid)
            {
                for(l = j; l <= right; l++)
                    temp[k++] = p[l];
            }
            else
            {
                for(l = i; l <= mid; l++)
                {
                    temp[k++] = p[l];
                }
            }

            for(l = left; l <= right; l++)
            {
                p[l] = temp[l];
            }
        }

        static void MergeSort(People[] p, int left, int right)
        {
            int mid;

            if (left < right)
            {
                mid = (left + right) / 2;
                MergeSort(p, left, mid);
                MergeSort(p, mid + 1, right);
                Merge(p, left, mid, right);
            }
        }

        static void Main(string[] args)
        {
            using var input = new System.IO.StreamReader(Console.OpenStandardInput());
            using var output = new System.IO.StreamWriter(Console.OpenStandardOutput());

            int n = int.Parse(input.ReadLine());
            People[] people = new People[n];

            for (int i = 0; i < n; i++)
            {
                string[] s = input.ReadLine().Split();

                people[i].age = int.Parse(s[0]);
                people[i].name = s[1];
            }

            MergeSort(people, 0, n-1);

            foreach (People person in people)
            {
                output.WriteLine($"{person.age} {person.name}");
            }

        }
    }

}

하.. 열심히 합병정렬 했더니 메모리초과여서 그냥 Array.Sort 쓸거임 ㅡㅡ

코드

namespace SongE
{
    struct People
    {
        public int id;
        public int age;
        public string name;
    }
    public class Program
    {
        static void Main(string[] args)
        {
            using var input = new System.IO.StreamReader(Console.OpenStandardInput());
            using var output = new System.IO.StreamWriter(Console.OpenStandardOutput());

            int n = int.Parse(input.ReadLine());
            People[] people = new People[n];

            for (int i = 0; i < n; i++)
            {
                string[] s = input.ReadLine().Split();

                people[i].id = i;
                people[i].age = int.Parse(s[0]);
                people[i].name = s[1];
            }

            Array.Sort(people, (a,b) => {
                return a.age == b.age ? a.id - b.id : a.age - b.age;
            });

            foreach (People person in people)
            {
                output.WriteLine($"{person.age} {person.name}");
            }

        }
    }

}