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

 

문제 분석

• N개의 서로 다른 양의 정수가 저장된 배열 A
• 병합 정렬로 배열 A의 오름차순을 정렬할 경우 배열 A에 k번째 저장되는 수를 구하라
• 저장 횟수가 k보다 작으면 -1 출력

 

정답 코드

1차 - 실패

import sys
input = sys.stdin.readline

global cnt

def merge_sort(arr, k) :
    if len(arr) < 2 :
        return arr

    mid = len(arr) // 2
    low_arr = merge_sort(arr[:mid], k)
    high_arr = merge_sort(arr[mid:], k)

    merged_arr = []
    l=h=0
    cnt = 0
    while l < len(low_arr) and h < len(high_arr) :
        if low_arr[l] < high_arr[h] :
            merged_arr.append(low_arr[l])
            cnt += 1
            l += 1
        else :
            merged_arr.append(high_arr[h])
            cnt += 1
            h += 1
        if cnt == k :
            print(merged_arr[-1])
    merged_arr += low_arr[l:]
    merged_arr += high_arr[:h]
    if cnt < k:
        print(-1)
    return merged_arr

n, k = map(int, input().split())
arr = list(map(int, input().split()))
merge_sort(arr, k)

 

다른 사람 코드 1

import sys
input = sys.stdin.readline

def merge_sort(A, p, r) :
    if p < r :
        q = (p+r) // 2
        merge_sort(A, p, q)
        merge_sort(A, q+1, r)
        merge(A, p, q, r)

def merge(A, p, q, r) :
    global cnt, res
    l = p
    h = q+1
    tmp = []

    while l <= q and h <= r :
        if A[l] < A[h] :
            tmp.append(A[l])
            l += 1
        else :
            tmp.append(A[h])
            h += 1

    while l <= q : # 배열 왼쪽 부분이 남은 경우
        tmp.append(A[l])
        l += 1

    while h <= r : # 배열 오른쪽 부분이 남은 경우
        tmp.append(A[h])
        h += 1

    l = p
    t = 0

    while l <= r : # 결과를 A[p~r]에 저장
        A[l] = tmp[t]
        cnt += 1
        if cnt == k :
            res = A[l]
            break
        l += 1
        t += 1

n,k = map(int, input().split())
A = list(map(int, input().split()))
cnt = 0
res = -1
merge_sort(A, 0, n-1)
print(res)