백준 24060 - 병합정렬1

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

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

 

 

 

문제를 풀기에 앞서, 병합정렬에 대해 공부해보도록 하자.

https://kangworld.tistory.com/m/74

[Algorithm] 병합 정렬(Merge Sort) 코드와 시간 복잡도

 

포스팅에 자세하게 나와있으므로 참고할 것!

 

위의 포스팅과 사진을 참고하면 병합정렬이 어떻게 이루어지는지 대충 짐작할 수 있다.

n개의 데이터가 들어가있는 배열이 있다고 하자.

배열을 크기가 1로 각각 쪼갠 후, 2개씩 병합하여 정렬한다.

또 4개, 8개.. 이렇게 2의 n승으로 크기를 늘려 병합하면서 정렬한다.

 

백준에 다행히 의사코드가 나와있어서 약간의 수정만을 가지고 문제를 풀 수 있었는데, 만약 의사코드가 없었다면 분명히 손도 못 댔을 것이다.

 아직 의사코드를 보지 않고 구현할 실력은 되지 않기 때문에, 의사코드의 의미를 해석하고 문제를 이해하는데 우선을 두고 나중에 의사코드 없이 병합정렬을 구현해보는 연습을 해보도록 하자.

 

def merge_sort(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)  # 병합

def merge(A, p, q, r):  # 병합 알고리즘
    global cnt, result
    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
    
    # 위의 전체 코드 실행 결과, 새로운 저장장소 tmp에서 기존 배열로 복사시킴
    while i <= r:
        A[i] = tmp[t]
        cnt += 1
        if cnt == K:
            result = A[i]
            break
        i += 1
        t += 1



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