(Python/🥈4)24060번: 알고리즘 수업 - 병합 정렬 1

문제 출처:https://www.acmicpc.net/problem/24060

24060번: 알고리즘 수업 - 병합 정렬 1

문제 풀이:

첫 번째 시도 

import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

def merge_sort(list):
    n = len(list)
    if n <= 1:
        return list
    mid = (n+1)//2  # 중간을 기준으로 두 그룹으로 나눔
    g1 = merge_sort(list[:mid]) # 재귀 호출로 첫 번째 그룹을 정렬  처음 부터 mid 까지
    g2 = merge_sort(list[mid:]) # 재귀 호출로 두 번째 그룹을 정렬  mid 부터 끝까지
    result = []
    while g1 and g2:  # 두 그룹에 모두 자료가 남아 있는 동안 반복
        if g1[0] < g2[0]: # 두 그룹의 맨 앞 자료 값을 비교
            x = g1.pop()
            result.append(x)
            res.append(x)
        else:
            x = g2.pop(0)
            result.append(x)
            res.append(x)
    while g1:
        x =g1.pop(0)
        result.append(x)
        res.append(x)
    while g2:
        x = g2.pop(0)
        result.append(x)
        res.append(x)
    return result

n, k = map(int,input().split())
a = list(map(int,input().split()))
res = []
merge_sort(a)

if len(res) >= k:
    print(res[k-1])
else:
    print(-1)

답은 맞지만 시간 초과가 나온다

 

두 번째 시도

def merge_sort(list):
    n = len(list)

    if n <= 1:
        return list
    mid = (n+1)//2  # 중간을 기준으로 두 그룹으로 나눔
    g1 = merge_sort(list[:mid]) # 재귀 호출로 첫 번째 그룹을 정렬  처음 부터 mid 까지
    g2 = merge_sort(list[mid:]) # 재귀 호출로 두 번째 그룹을 정렬  mid 부터 끝까지
    result, i, j =[], 0, 0

    while i < len(g1) and j < len(g2):  
        if g1[i] < g2[j]: 
            result.append(g1[i])
            res.append(g1[i])
            i += 1
        else:
            result.append(g2[j])
            res.append(g2[j])
            j+=1
            
    result.extend(g1[i:])
    result.extend(g2[j:])

    res.extend(g1[i:])
    res.extend(g2[j:])

    return result

N, M = map(int,input().split())
arr = list(map(int,input().split()))
res = []

merge_sort(arr)
print(res[M-1]) if len(res) >= M else print(-1)

 

잘 안 풀려서 https://my-coding-notes.tistory.com/581?category=957026 도 참고

mid 는 앞이 크도록 병합해서 +1 해준다.

 

res는 병합 과정을 리스트로 만든것이다.

result 는 정렬한 값을 리스트로 만들어서 리턴해줌