글 읽기 - 파이썬으로 짠 Merge Sort 왜 시간초과일까요?

h4ckjk 7년 전 1

c언어에서 짰을 때랑 흡사하게 알고리즘 구성하여 짰는데,

시간초과가 뜨네요 ㅠ-ㅠ

def merge_sort(a, l, r) :
    if(l < r) :
        m = (l + r) / 2
        merge_sort(a, l, m)
        merge_sort(a, m+1, r)
        return merge(a,l,m,r)

def merge(a, l, m, r) :

    i = l
    j = m + 1

    res = list()

    while i <= m and j <= r :
        if a[i] <= a[j] :
            res.append(a[i])
            i += 1
        else :
            res.append(a[j])
            j += 1

    if i > m :
        for remainder in range(j, r+1, 1) :
            res.append(a[remainder])
    else :
        for remainder in range(i, m+1, 1):
            res.append(a[remainder])

    for change in range(l, r+1, 1) :
        a[change] = res[change-l]

    return a

n = int(raw_input())
num = list()

for i in range(n) :
    num.append(int(raw_input()))

x = merge_sort(num, 0, num.__len__() -1)

for i in range(x.__len__()) :
    print x[i]

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

문제

문제

출처

ICPC

파이썬으로 짠 Merge Sort 왜 시간초과일까요?

h4ckjk 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말