[PS] 병합 정렬(mergeSort) 문제에서 시간 초과 오류 발생하는 경우

BOJ-2751, BOJ-24060
병합 정렬 알고리즘에서 시간 초과 오류가 발생하는 경우 해결하는 방법이다.


시간 초과가 발생하는 코드

import sys
n = int(sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))
def merge(a,p,q,r):
        temp = [0 for _ in range(n)]  
        # temp를 merge 함수 안에서 선언하면 재귀적으로 호출 될 때마다 선언되므로 시간이 낭비된다!!  
        i = p; j = q+1; t = 0
        while i <= q and j <= r:
            if a[i] > a[j]: temp[t] = a[j]; j += 1; t += 1 
            else: temp[t] = a[i]; i += 1; t += 1
        while i <= q: temp[t] = a[i]; i += 1; t += 1
        while j <= r: temp[t] = a[j]; j += 1; t += 1
        i = p; t = 0
        while i <= r: a[i] = temp[t]; i += 1; t += 1
def mergeSort(a,p,r):
    if p < r:
        q = (p+r)//2
        mergeSort(a,p,q)
        mergeSort(a,q+1,r)
        merge(a,p,q,r)
    

정답 코드

import sys
n = int(sys.stdin.readline().split())
temp = [0 for _ in range(n)]  # temp를 global로 선언한 후
a = list(map(int, sys.stdin.readline().split()))
def merge(a,p,q,r):
        global temp  # 호출하여 사용하면 위와 같은 시간 낭비를 단축할 수 있다!!
        i = p; j = q+1; t = 0
        while i <= q and j <= r:
            if a[i] > a[j]: temp[t] = a[j]; j += 1; t += 1 
            else: temp[t] = a[i]; i += 1; t += 1
        while i <= q: temp[t] = a[i]; i += 1; t += 1
        while j <= r: temp[t] = a[j]; j += 1; t += 1
        i = p; t = 0
        while i <= r: a[i] = temp[t]; i += 1; t += 1
def mergeSort(a,p,r):
    if p < r:
        q = (p+r)//2
        mergeSort(a,p,q)
        mergeSort(a,q+1,r)
        merge(a,p,q,r)