글 읽기 - 파이썬) 병합정렬 시간초과... 뭐가 문제일까요?

tofan123 2년 전 0

위 코드는 제가 작성한 거구요. 2퍼에서 시간초과로 통과하지 못했습니다. 하단의 코드는 제가 3일동안 끙끙 앓아서 결국 본 답지입니다 ㅠㅠ 어떤 차이가 있는걸까요??

# SILVER5
# 주의할 점 : N의 최대 수가 1,000,000이다
# 시간 초과가 뜬 코드
def merge_sort(arr, start, end):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid], start, mid-1)
    right = merge_sort(arr[mid:], mid, end)

    merged = []
    while len(left) > 0 and len(right) > 0:
        if left[0] < right[0]:
            merged.append(left.pop(0))
        else:
            merged.append(right.pop(0))

    if len(left) > 0:
        while len(left) > 0:
            merged.append(left.pop(0))
    if len(right) > 0:
        while len(right) > 0:
            merged.append(right.pop(0))
    return merged


# 정답 코드는 다음과 같다.
def merge_sort2(array):
    if len(array) <= 1:
        return array
    mid = len(array) // 2
    left = merge_sort(array[:mid])
    right = merge_sort(array[mid:])

    i, j, k = 0, 0, 0 # i는 left의 pointer, j는 right의 pointer이다. k는 array의 인덱스이다.

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            array[k] = left[i]
            i += 1
        else:
            array[k] = right[j]
            j += 1
        k += 1

    if i == len(left):
        while j < len(right):
            array[k] = right[j]
            j += 1
            k += 1
    elif j == len(right):
        while i < len(left):
            array[k] = left[i]
            i += 1
            k += 1
    return array


N = int(input())
arr = []
for i in range(N):
    number = int(input())
    arr.append(number)

# result = merge_sort(arr, 0, len(arr) - 1)
result = merge_sort2(arr)

for number in result:
    print(number)

lcr7324 2년 전 1

list.pop(0)는 O(N)의 시간복잡도를 가집니다.

tofan123 2년 전 0

감사합니다! 저 부분을 수정해서 다시 제출해 봐야겠습니다 ㅠㅠ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

파이썬) 병합정렬 시간초과... 뭐가 문제일까요?

tofan123 2년 전 0

lcr7324 2년 전 1

tofan123 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말