[C#] 10814번: 나이순 정렬

목차

---

백준 단계별로 풀어보기

25.10.26

13단계: 정렬

10814번: 나이순 정렬

문제 링크 : https://www.acmicpc.net/problem/10814

 

문제를 풀기 위해 알아야 할 개념

>> 튜플, 병합/합병 정렬(Merge Sort)

: 아래 링크에 자세히 설명해두었다.

 

[C#] 11650번: 좌표 정렬하기

 

문제 풀이

: 병합 정렬을 활용하여 나이가 증가하는 순으로 정렬하는데, 입력값을 담을 튜플에 index 값을 추가하여 가입한 순서를 알 수 있게 하고, 만약 나이가 같다면 튜플의 index 가 작은 사람이 앞에 오는 순서로 정렬한다.

1. 정렬한 값을 임시로 담을 튜플형 배열 temp 를 전역에 선언한다.
2. StreamReader를 통해 입력값을 받아 int값으로 변환하여 회원 수를 담을 변수 count 에 담고, 회원의 나이, 이름, index 번호를 담을 튜플형 배열 arr 를 count 의 크기로 초기화하고, 배열 temp 를 count 의 크기로 초기화한다.
3. for 반복문을 통해 StreamReader로 받은 나이, 이름, index 를 배열 arr 에 담는다.
4. 만든 MergeSort 함수를 통해 배열 arr 를 정렬한다.
   •     MergeSort 및 Merge 함수를 만들 때 튜플형 배열을 매개변수로 받도록 한다.
   •     두 회원을 비교할 때, 나이를 먼저 비교하여 나이 순으로 정렬하고, 만약 나이가 같다면 index 를 비교하여 가입한 순으로 정렬한다.
5. for 반복문을 통해 arr 의 나이와 이름을 StringBuilder에 담고 나서 이를 출력한다.

 

정답 코드

using System.IO;
using System.Text;

class Backjoon
{
    static (int, string, int)[] temp;
    
    static void Main(string[] args)
    {
        using var sr = new StreamReader(Console.OpenStandardInput());
        using var sw = new StreamWriter(Console.OpenStandardOutput());
        StringBuilder sb = new StringBuilder();
        
        int count = int.Parse(sr.ReadLine());
        (int age, string name, int index)[] arr = new (int, string, int)[count];
        temp = new (int, string, int)[count];

        for (int i = 0; i < count; i++)
        {
            string[] input = sr.ReadLine().Split();
            arr[i] = (int.Parse(input[0]), input[1], i);
        }
        
        MergeSort(arr, 0, count - 1);

        for (int i = 0; i < count; i++)
        {
            sb.Append(arr[i].age).Append(' ').Append(arr[i].name).Append('\n');
        }
        sw.Write(sb);
    }

    static void MergeSort((int age, string name, int index)[] arr, int left, int right)
    {
        if (left < right)
        {
            int mid = (left + right) / 2;

            MergeSort(arr, left, mid);
            MergeSort(arr, mid + 1, right);
            Merge(arr, left, mid, right);
        }
    }

    static void Merge((int age, string name, int index)[] arr, int left, int mid, int right)
    {
        int i = left;
        int j = mid + 1;
        int k = left;

        while (i <= mid && j <= right)
        {
            if (arr[i].age < arr[j].age)
                temp[k++] = arr[i++];
            else if (arr[i].age == arr[j].age)
            {
                if (arr[i].index < arr[j].index)
                    temp[k++] = arr[i++];
                else
                    temp[k++] = arr[j++];
            }
            else
                temp[k++] = arr[j++];
        }

        while (i <= mid)
            temp[k++] = arr[i++];
        while (j <= right)
            temp[k++] = arr[j++];

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