[C#] 백준 10814번 나이순 정렬

[ 문제 ]

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

 

[ 코드 ]

1. 내 코드(OrderBy메서드 사용)

StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));

int n = int.Parse(sr.ReadLine());
List<Tuple<int, string>> sList = new List<Tuple<int, string>>();

for (int i = 0; i < n; i++)
{
    string[] s = sr.ReadLine().Split();
    var inputUser = Tuple.Create<int, string>(int.Parse(s[0]), s[1]);
    sList.Add(inputUser);
}

sList = sList.OrderBy(x => x.Item1).ToList();

foreach (var s in sList)
{
    sw.WriteLine($"{s.Item1} {s.Item2}");
}

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

 

2. 병합정렬 구현

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
        var sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));

        int n = int.Parse(sr.ReadLine());
        List<Tuple<int, string>> sList = new List<Tuple<int, string>>();

        for (int i = 0; i < n; i++)
        {
            string[] s = sr.ReadLine().Split();
            var inputUser = Tuple.Create<int, string>(int.Parse(s[0]), s[1]);
            sList.Add(inputUser);
        }

        sList = StableSort(sList);

        foreach (var s in sList)
        {
            sw.WriteLine($"{s.Item1} {s.Item2}");
        }

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

    // 병합 정렬
    static List<Tuple<int, string>> StableSort(List<Tuple<int, string>> list)
    {
        // 리스트의 크기가 1 이하이면 정렬할 필요가 없음
        if (list.Count <= 1)
            return list;

        // 리스트를 반으로 나눔
        int mid = list.Count / 2;
        var left = new List<Tuple<int, string>>();
        var right = new List<Tuple<int, string>>();

        // 왼쪽과 오른쪽 부분 리스트로 분할
        for (int i = 0; i < mid; i++)
            left.Add(list[i]);
        for (int i = mid; i < list.Count; i++)
            right.Add(list[i]);

        // 각 부분 리스트를 재귀적으로 정렬
        left = StableSort(left);
        right = StableSort(right);

        // 정렬된 부분 리스트들을 병합하여 결과를 반환
        return Merge(left, right);
    }

    // 두 리스트를 병합하는 메서드
    static List<Tuple<int, string>> Merge(List<Tuple<int, string>> left, List<Tuple<int, string>> right)
    {
        var result = new List<Tuple<int, string>>();

        // 양쪽 리스트가 비어있지 않을 때까지 반복
        while (left.Count > 0 && right.Count > 0)
        {
            // 나이를 기준으로 더 작은 요소를 결과에 추가
            if (left[0].Item1 <= right[0].Item1)
            {
                result.Add(left[0]);
                left.RemoveAt(0);
            }
            else
            {
                result.Add(right[0]);
                right.RemoveAt(0);
            }
        }

        // 남은 요소들을 결과에 추가
        result.AddRange(left);
        result.AddRange(right);

        return result;
    }
}

 

[ 실행화면 ]

case: 1

---

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

10814번: 나이순 정렬

병합정렬 공부하려고 블로그에 올린다.. 힙정렬은 아직도 좀 어려운듯..