[C#] 백준 24060번 알고리즘 수업 - 병합 정렬 1

[ 문제 ]

오늘도 서준이는 병합 정렬 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

N개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 병합 정렬로 배열 A를 오름차순 정렬할 경우 배열 A에 K 번째 저장되는 수를 구해서 우리 서준이를 도와주자.

크기가 N인 배열에 대한 병합 정렬 의사 코드는 다음과 같다.

merge_sort(A[p..r]) { // A[p..r]을 오름차순 정렬한다.
    if (p < r) then {
        q <- ⌊(p + r) / 2⌋;       // q는 p, r의 중간 지점
        merge_sort(A, p, q);      // 전반부 정렬
        merge_sort(A, q + 1, r);  // 후반부 정렬
        merge(A, p, q, r);        // 병합
    }
}

// A[p..q]와 A[q+1..r]을 병합하여 A[p..r]을 오름차순 정렬된 상태로 만든다.
// A[p..q]와 A[q+1..r]은 이미 오름차순으로 정렬되어 있다.
merge(A[], p, q, r) {
    i <- p; j <- q + 1; t <- 1;
    while (i ≤ q and j ≤ r) {
        if (A[i] ≤ A[j])
        then tmp[t++] <- A[i++]; # tmp[t] <- A[i]; t++; i++;
        else tmp[t++] <- A[j++]; # tmp[t] <- A[j]; t++; j++;
    }
    while (i ≤ q)  // 왼쪽 배열 부분이 남은 경우
        tmp[t++] <- A[i++];
    while (j ≤ r)  // 오른쪽 배열 부분이 남은 경우
        tmp[t++] <- A[j++];
    i <- p; t <- 1;
    while (i ≤ r)  // 결과를 A[p..r]에 저장
        A[i++] <- tmp[t++]; 
}

 

[ 코드 ]

1. 내 코드

using System;
using System.Collections.Generic;

class Program
{
    static List<int> MergeSort(List<int> arr)
    {
        // 길이가 1 이하시 반환
        if (arr.Count <= 1)
            return arr;

        // 반으로 나누기 위한 mid 계산
        int mid = (arr.Count + 1) / 2;

        // 리스트를 반으로 나눠 각각의 부분 리스트에 재귀적으로 합병 정렬 적용
        List<int> lowArr = MergeSort(arr.GetRange(0, mid));
        List<int> highArr = MergeSort(arr.GetRange(mid, arr.Count - mid));

        // 정렬된 결과를 저장할 리스트
        List<int> sortedArr = new List<int>();

        // lowArr와 highArr를 비교하면서 합병
        int l = 0, h = 0;
        while (l < lowArr.Count && h < highArr.Count)
        {
            // lowArr과 highArr에서 작은 값을 선택하여 sortedArr에 추가
            if (lowArr[l] <= highArr[h])
            {
                sortedArr.Add(lowArr[l]);
                ans.Add(lowArr[l]); // 정렬된 값을 ans 리스트에 추가
                l++;
            }
            else
            {
                sortedArr.Add(highArr[h]);
                ans.Add(highArr[h]); // 정렬된 값을 ans 리스트에 추가
                h++;
            }
        }

        // 남은 요소들을 sortedArr에 추가
        while (l < lowArr.Count)
        {
            sortedArr.Add(lowArr[l]);
            ans.Add(lowArr[l]); // 정렬된 값을 ans 리스트에 추가
            l++;
        }

        while (h < highArr.Count)
        {
            sortedArr.Add(highArr[h]);
            ans.Add(highArr[h]); // 정렬된 값을 ans 리스트에 추가
            h++;
        }

        // 정렬된 리스트 반환
        return sortedArr;
    }

    // 결과 값 저장을 위한 정적 리스트
    static List<int> ans = new List<int>();

    static void Main(string[] args)
    {

        string[] inputs = Console.ReadLine().Split();
        int N = int.Parse(inputs[0]); 
        int K = int.Parse(inputs[1]);

        MergeSort(new List<int>(Array.ConvertAll(Console.ReadLine().Split(), int.Parse)));
        Console.WriteLine((K <= ans.Count) ? ans[K - 1].ToString() : "-1");
    }
}

 

2. 다른 사람 코드

using System.Text;

namespace ConsoleApp1
{
    internal class Program
    {
        static int target; 
        static int[] a;
        static StringBuilder sb = new StringBuilder(); 

        public static void Main(string[] args)
        {
            StreamReader input = new StreamReader(
                new BufferedStream(Console.OpenStandardInput()));
            StreamWriter output = new StreamWriter(
                new BufferedStream(Console.OpenStandardOutput()));

            int[] arr = Array.ConvertAll(input.ReadLine().Split(' '), int.Parse);
            int n = arr[0]; 
            target = arr[1]; 
            a = Array.ConvertAll(input.ReadLine().Split(' '), int.Parse); 

            // 이분 탐색 함수 호출
            find(0, n - 1);

            // 결과가 없을 경우 -1 출력
            if (sb.Length == 0)
                sb.Append("-1");

            output.Write(sb);

            input.Close();
            output.Close();
        }

        // 이분 탐색 함수
        static void find(int start, int end)
        {
            // 범위가 잘못되었거나 target이 0 이하일 경우 종료
            if (start == end || target <= 0) return;

            // 중간 값 계산
            int mid = (start + end) / 2;

            // 왼쪽과 오른쪽에 대해 재귀적으로 호출
            find(start, mid);
            find(mid + 1, end);

            // target이 유효하고 범위 내에 있을 때
            if (target > 0 && target <= end - start + 1)
            {
                // 배열의 일부를 정렬하고 결과에 추가
                Array.Sort(a, start, end - start + 1);
                sb.Append($"{a[start + target - 1]}");
            }

            // target 갱신
            target -= end - start + 1;
        }
    }
}

 

나중에 봤을때 주석보고 이해 쉽게 하기위해서 주석을 달아놨다.......

이러면 별로 안좋으려나

 

[ 실행화면 ]

case: 1

case: 2

 

 

 

 

 

---

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