[BOJ] 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을 출력한다.

📚 예제

Ex1)

5 7
4 5 1 3 2

3

4 5 1 3 2 -> 4 5 1 3 2 -> 4 5 1 3 2 -> 1 5 1 3 2 -> 1 4 1 3 2 -> 1 4 5 3 2 -> 1 4 5 2 2 -> 1 4 5 2 3 -> 1 4 5 2 3 -> 1 2 5 2 3 -> 1 2 3 2 3 -> 1 2 3 4 3 -> 1 2 3 4 5. 총 12회 저장이 발생하고 일곱 번째 저장되는 수는 3이다.

Ex2)

5 13
4 5 1 3 2

-1

저장 횟수 12가 K 보다 작으므로 -1을 출력한다.

📌 풀이

백준에 적힌 의사코드를 따라서 코드를 작성하면 함수를 만드는데 큰 어려움은 없다.
문제는 정렬되는 과정에서 K번째로 저장되는 수를 구하는 것이다.
생각한 방법은 2가지였다.

1. merge함수에서 병합하는 과정에서 k번째에 저장되는 수를 바로 출력
   : 이 방법은 만약 저장 횟수가 k번째보다 작으면 -1출력을 어떻게 할지 생각하기 힘들어서 pass했다.

2. merge함수에서 저장되는 수를 리스트에 모두 저장
   : 이 방법을 사용하면 총 저장 횟수를 알 수 있고, 리스트를 이용해 k번째 저장 수를 찾기 편하다.
   문제는 파이썬의 경우 각 함수 안에서 따로따로 global을 선언해야하는데, 재귀 함수라 global 변수가 자꾸 초기화 되는 것이다.
   그래서을 사용해서 특정한 경우에만 리스트 ans가 초기화되도록 했더니 그런 문제가 사라졌고, list ans를 return 받아 k번째 저장되는 수를 구하였다.
   너무 어거지로 구한 것 같아서 다음에 더 좋은 방법이 생각난다면 바꿔야겠다.

🔑 python 코드

import sys

def merge_sort(ary,left,right): 
    global ans
    if((left == 0)and (right == len(ary)-1)):
        ans = []
    if(left<right):
        mid = (left+right)//2
        merge_sort(ary,left,mid)
        merge_sort(ary,mid+1,right)
        return merge(ary,left,mid,right)

def merge(ary,left,mid,right):
    global ans
    i = left
    j = mid+1
    t = left
    temp = []
    while((i<=mid) and (j <= right)):
        if(ary[i] <= ary[j]):
            temp.append(ary[i])
            t+=1
            i+=1
        else:
            temp.append(ary[j])
            t+=1
            j+=1

    while(i <= mid):
        temp.append(ary[i])
        t+=1
        i+=1

    while(j <= right):
        temp.append(ary[j])
        t+=1
        j+=1

    i = left
    t = 0

    while(i<=right):
        ary[i] = temp[t]
        ans.append(ary[i])
        i+=1
        t+=1
    return ans

N, K = map(int, sys.stdin.readline().split())
ary = [int(x) for x in sys.stdin.readline().split()]
ans = merge_sort(ary,0,len(ary)-1)

if(len(ans)-1 < K-1):
    print(-1)
else:
    print(ans[K-1])

c언어랑 전역 변수 선언하는 방법이 달라서 헷갈렸다. 전역 변수 다시 공부해야징