[백준] 24060: 알고리즘 수업 - 병합 정렬 1 - 파이썬[python]

수도코드를 이해하는 게 관건이었던 문제,, 사실 100% 이해하지 못해도 문제를 풀 수 있어서 먼저 문제를 풀었다.. 그래도 병합정렬을 이해하면 분명 도움이 될 것 같아 손으로 엄청 써보며 이해를 했다.(좀 복잡하게 병합정렬을 정의한 느낌..)

병합 정렬

• 병합정렬을 리스트를 계속 반으로 쪼개 나가서 더 이상 쪼갤 수 없을 때까지 즉, 모든 리스트의 원소의 1일 때까지 반복한다.
• 이제 각 리스트를 2개씩 묶어서 크기를 비교하고 작은 걸 먼저 배열에 넣어 순서대로 정렬하면서 두 리스트를 합친다.

코드

def merge_sort(A, p, r): # A[p..r]을 오름차순 정렬한다.
    if p < r:
        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]은 이미 오름차순으로 정렬되어 있다.
def merge(A, p, q, r):
    i = p
    j = q+1
    tmp = []
    
    while i<=q and j<=r:
        if A[i] <= A[j]:
            tmp.append(A[i])
            i += 1
        else:
            tmp.append(A[j])
            j += 1
    while i <= q: # 왼쪽 배열 부분이 남은 경우
        tmp.append(A[i])
        i += 1
    while j <= r: # 오른쪽 배열 부분이 남은 경우
        tmp.append(A[j])
        j += 1
    
    i = p
    t = 0
    while i <= r: # 결과를 A[p..r]에 저장
        A[i] = tmp[t]
        i += 1
        t += 1

N, K = map(int, input().split())
A = list(map(int, input().split()))
merge_sort(A, 0, N-1)

• 수도 코드를 파이썬으로 작성한 코드이다.(병합 정렬만 작성)
• 병렬 정렬은 실질적으로 merge에서 모두 이루어진다고 보인다.
  merge_sort에서 적당히 쪼개고 merge에서 두 원소들을 비교하며 원래 리스트 A를 정렬한 상태로 다시 저장하는 것이다.
• 즉, merge함수에서 tmp.append하는 것들은 정렬하는 거고 아래 코드가 실질적으로 정렬된 원소를 저장하는 과정이다.

 while i <= r: # 결과를 A[p..r]에 저장
        A[i] = tmp[t]
        i += 1
        t += 1

• 그래서 위 코드에서 전역변수 global을 통해 저장하는 횟수를 기록한다.
• count가 우리가 찾고자 하는 K가 된 순간 result에 저장할 원소의 값으로 덮어씌우고 break한다.
• 결국 저장횟수가 K보다 작으면 count==K가 되는 일이 없으므로 result는 그대로 -1이다.
• result를 반환하면 끝.

정답 코드

import sys
input = sys.stdin.readline

def merge_sort(A, p, r): # A[p..r]을 오름차순 정렬한다.
    if p < r:
        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]은 이미 오름차순으로 정렬되어 있다.
def merge(A, p, q, r):
    i = p
    j = q+1
    tmp = []
    global count, result
    
    while i<=q and j<=r:
        if A[i] <= A[j]:
            tmp.append(A[i])
            i += 1
        else:
            tmp.append(A[j])
            j += 1
    while i <= q: # 왼쪽 배열 부분이 남은 경우
        tmp.append(A[i])
        i += 1
    while j <= r: # 오른쪽 배열 부분이 남은 경우
        tmp.append(A[j])
        j += 1
    
    i = p
    t = 0
    while i <= r: # 결과를 A[p..r]에 저장
        A[i] = tmp[t]
        count += 1
        if count == K:
            result = A[i]
            break
        i += 1
        t += 1

N, K = map(int, input().split())
A = list(map(int, input().split()))
count = 0
result = -1
merge_sort(A, 0, N-1)
print(result)

결과