알고리즘 수업 - 병합 정렬 1 풀이

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

백준 재귀 4단계 - 24060번 알고리즘 수업 - 병합 정렬 1을 풀어보았다.

 

풀이: 병합 정렬을 구현하고, k번째를 출력하면 된다.

C++의 경우, https://codnote.tistory.com/3 를 참고했다.

파이썬의 경우, https://velog.io/@wngud4950/%EB%B0%B1%EC%A4%80-24060.-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%88%98%EC%97%85-%EB%B3%91%ED%95%A9%EC%A0%95%EB%A0%AC1 를 참고했다.

 

C++

#include <iostream>
using namespace std;

int* A;
int* tmp;
int N, cnt = 0, K = 0, result = -1;

void merge(int A[], int p, int q, int r)
{
    int i = p, j = q + 1, t = 1;
  
    while (i <= q && j <= r)
    {
        if (A[i] <= A[j])
            tmp[t++] = A[i++];
        else
            tmp[t++] = A[j++];
    }
    while (i <= q) 
        tmp[t++] = A[i++];

    while (j <= r) 
        tmp[t++] = A[j++];

    i = p, t = 1;
    while (i <= r) 
    {
        A[i++] = tmp[t++];
        cnt++;
        if (cnt == K)
        {
            result = A[i - 1];
            break;
        }
    }
}

void merge_sort(int A[], int p, int r)
{
    if (p < r)
    {
        int q = (p + r) / 2;
        merge_sort(A, p, q);
        merge_sort(A, q + 1, r);
        merge(A, p, q, r);
    }
}

int main() {
    cin >> N >> K;
    A = new int[N + 1];
    tmp = new int[N + 1];
    for (int i = 0; i < N; i++)
        cin >> A[i];
    merge_sort(A, 0, N - 1);
    cout << result;
    delete[] A;
    delete[] tmp;
    return 0;
}

Python

def mergeSort(L):
    if len(L) == 1:
        return L
    mid = (len(L) + 1)//2
    left = mergeSort(L[:mid])
    right = mergeSort(L[mid:])
    L2 = []
    i = 0
    j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            L2.append(left[i])
            ans.append(left[i])
            i += 1
        else:
            L2.append(right[j])
            ans.append(right[j])
            j += 1
    while i < len(left):
        L2.append(left[i])
        ans.append(left[i])
        i += 1  
    while j < len(right):
        L2.append(right[j])
        ans.append(right[j])
        j += 1  
    return L2

n, k = map(int,input().split())
a = list(map(int,input().split()))
ans = []
mergeSort(a)
if len(ans) >= k: print(ans[k-1]) # 정렬된 순서대로 넣는다
else: print(-1)

Java