백준 24060번 알고리즘 수업 - 병합 정렬 1 | python

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

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++]; 
}

입력

첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 500,000), 저장 횟수 K(1 ≤ K ≤ 108)가 주어진다.

다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)

출력

배열 A에 K 번째 저장 되는 수를 출력한다. 저장 횟수가 K 보다 작으면 -1을 출력한다.

---

이번 문제는 문제에서 주어진 의사코드를 자신이 사용하는 언어로 잘 풀어 쓸 줄 아는지 물어보는 문제라고 할 수 있다.

병함 정렬에 대한 이해가 부족하더라도 문제를 해결할 수 있다. 그래서 그런지 딱히 설명할 내용은 없다.

어려운 부분이 있다면, K번째 저장되는 수가 어디에 위치하는 지 아는 것이다. 처음에는 정렬이 완료되는 시점에서 Counting 된다고 판단 했었는데, while Loop를 도는 과정에서 Counting이 된다는 걸 출력 해보면서 알게 되었다.

그래서 전체를 저장해서 index를 가져오기 보다는 저장 Counting이 될 때마다 m의 값을 줄여주며 m이 0이 되었을 때 저장되는 값을 answer에 저장 해주기고 했다.

저장되는 Count가 m보다 작은 경우에는 -1을 출력해야하므로 answer의 초기화 값을 -1로 해주어서 따로 지정하지 않아도 되도록 했다.

이번 코드는 딱히 설명을 붙이지 않았다.

 

import sys

input = sys.stdin.readline


def MergeSort(arr, s, e):
    if s < e:
        middle = (s + e) // 2
        MergeSort(arr, s, middle)
        MergeSort(arr, middle + 1, e)
        Merge(arr, s, middle, e)


def Merge(arr, s, middle, e):
    global answer, m
    start, end = s, middle + 1
    tmp = []

    while start <= middle and end <= e:
        if arr[start] <= arr[end]:
            tmp.append(arr[start])
            start += 1
        else:
            tmp.append(arr[end])
            end += 1

    while start <= middle:
        tmp.append(arr[start])
        start += 1

    while end <= e:
        tmp.append(arr[end])
        end += 1

    start, idx = s, 0
    while start <= e:
        arr[start] = tmp[idx]
        m -= 1
        if m == 0:
            answer = tmp[idx]
        idx += 1
        start += 1


answer = -1
n, m = map(int, input().split())
boards = list(map(int, input().split()))

MergeSort(boards, 0, n - 1)
print(answer)

 

커피 한 잔의 기부는 꾸준한 글을 쓸 수 있는 원동력이 됩니다.