백준 10814번 : 나이순 정렬 (C#)

오늘은 백준 10814번 문제인 나이순 정렬 문제를 C#으로 풀어봤다.
이 문제는 단순 정렬 문제처럼 보이지만, 안정 정렬(stable sort) 에 대한 개념이 중요하게 작용하는 문제였다.

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

🧩 문제 설명

회원들의 나이와 이름이 주어졌을 때, 아래 기준으로 정렬하라는 문제이다:

나이 순으로 오름차순 정렬

같은 나이일 경우에는 입력된 순서(가입한 순서) 를 유지

처음엔 List<(int, string)>로 받아서 Sort()를 했더니, 같은 나이일 때 입력 순서가 섞여버렸다.
→ 이 문제는 안정 정렬이 보장되지 않으면 틀리게 된다.

🛠️ 내가 처음 작성한 코드

List<(int age, string name)> people = new List<(int, string)>();

for (int i = 0; i < count; i++)
{
    string[] input = Console.ReadLine().Split();
    people.Add((int.Parse(input[0]), input[1]));
}

people.Sort();
foreach (var i in people)
    Console.WriteLine(i);

이렇게 작성하면 Tuple 기본 정렬 기준인 age → name 순으로는 정렬되지만,
같은 나이일 때 입력 순서가 유지되지 않아서 틀린다.

✅ 해결 방법

입력 순서를 기억하기 위해 index를 함께 저장하고,
LINQ의 OrderBy → ThenBy를 사용해서 안정 정렬을 보장해주면 된다.

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

namespace backjoon
{
    internal class Program
    {
        static void Main()
        {
            int count = int.Parse(Console.ReadLine());
            List<(int age, string name, int index)> people = new List<(int, string, int)>();

            for (int i = 0; i < count; i++)
            {
                string[] input = Console.ReadLine().Split();
                people.Add((int.Parse(input[0]), input[1], i)); // 입력 순서 i도 같이 저장
            }

            var sorted = people.OrderBy(p => p.age).ThenBy(p => p.index);

            foreach (var p in sorted)
                Console.WriteLine($"{p.age} {p.name}");
        }
    }
}

📌 배운 점

List.Sort()는 기본적으로 불안정 정렬이라, 입력 순서가 섞일 수 있다.

안정 정렬이 필요한 경우엔 OrderBy → ThenBy 또는 StableSort를 활용해야 한다.

튜플에 인덱스를 함께 넣는 방식은 나중에 정렬 기준이 여러 개일 때 꽤 유용하다!

🔚 마무리

정렬 문제는 단순히 오름차순, 내림차순만 생각했는데,
이번 문제를 통해 안정 정렬의 중요성을 다시금 느낄 수 있었다.
앞으로도 정렬 문제에서는 항상 “동일 기준일 때 순서 보장 여부”를 체크해야겠다.