[Baekjoon]백준 24060 알고리즘 수업 - 병합 정렬 1(실버 3) - Python

문제설명 1

문제설명 2

문제에서 알 수 있듯 병합 정렬을 이용하여 배열을 정렬하되, k를 입력받아 그때 저장되는 수를 찾아야한다

문제에서 병합 정렬에 대한 코드가 이미 나와있기 때문에 이를 활용하여 코드를 작성하면 된다

대신 의사코드와 파이썬은 약간 다르기 때문에 이에 맞게 적용하여야한다

 

tmp[t++] <- A[i++] 부분은 파이썬에서는 ++ 연산자를 지원하지 않고 append라는 연산자가 존재하므로

이를 활용하여 코드를 작성하는 것이 더 간단하다

그렇기 때문에 의사코드 마지막 while문 이전에 존재하는 t = 1 부분은 

우리는 리스트의 append로 해결하였기때문에 시작 지점이 0이 된다

 

그리고 그냥 병합정렬한 값을 출력하는 것이 아니라 k번째 저장된 값을 찾아야하기 때문에 

전역변수를 선언하여 횟수를 측정할 변수와 결과값을 저장할 변수를 만들어준다

결과값을 저장할 때는 값을 찾은 경우에는 찾은 값을 넣고 아닌 경우에는 -1을 출력해야하므로

처음에 -1을 저장해두면 추후에 추과과정 없이 결과값을 출력가능하다

def merge_sort(A, p, r):
    if p < r:
        q = (p + r) // 2
        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 # 의사코드에서는 t가 1로 시작하지만 해당 코드는 배열에 append로 삽입하므로 0부터 시작
    while i <= r:
        A[i] = tmp[t]
        cnt += 1
        if cnt == save_count:
            result = A[i]
            break
        i += 1
        t += 1
        
size, save_count = map(int, input().split())
array = list(map(int, input().split()))
cnt = 0
result = -1
merge_sort(array, 0, size - 1)
print(result)

전역 변수를 사용하지 않고 함수의 틀을 약간 변형함과 동시에 결과를 찾으면 조기종료되도록 하는 코드도 작성하였다

def merge_sort(A, p, r, save_count, cnt):
    result = -1
    if p < r:
        q = (p + r) // 2
        result, cnt = merge_sort(A, p, q, save_count, cnt)
        if result != -1:  # 이미 결과를 찾은 경우 조기 종료
            return result, cnt
        result, cnt = merge_sort(A, q + 1, r, save_count, cnt)
        if result != -1:  # 이미 결과를 찾은 경우 조기 종료
            return result, cnt
        result, cnt = merge(A, p, q, r, save_count, cnt)
    return result, cnt

def merge(A, p, q, r, save_count, cnt):
    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
    result = -1
    while i <= r:
        A[i] = tmp[t]
        cnt += 1
        if cnt == save_count:
            result = A[i]
            break
        i += 1
        t += 1
    return result, cnt

size, save_count = map(int, input().split())
array = list(map(int, input().split()))
result, _ = merge_sort(array, 0, size - 1, save_count, 0)
print(result)

merge_sort()부분에서 값을 찾으면 더 빨리 종료되도록 하였다

제출하였을때 확실히 시간의 차이점이 존재함을 확인할 수 있다

시간이 더 적게 걸린 코드가 두번째 코드이다