글 읽기 - Python3 Merge sort 시간 초과 (Pypy3로는 해결)

Zeta611 5년 전 0

아래의 iterative한 merge sort 알고리즘을 python 3로 작성해보았는데, 시간 초과가 떠서 질문을 찾아보았다가 pypy3로 바꿔보라는 말이 있어서 그렇게 했더니 통과가 되네요...

CPython으로 merge sort 구현을 해서 시간 초과가 안 나올 수는 없나요?

가능하다면, 아래 제 코드에는 어떤 문제가 있는 것인가요?

import sys

def merge_sort_iter(a):
    n = len(a)
    i = 2
    while i < n * 2:
        for j in range(0, n, i):
            llim = min(j + i // 2, n) - j
            rlim = min(j + i, n) - (j + i // 2)
            left = a[j:j + llim]
            right = a[j + i // 2:j + i // 2 + rlim]
            ileft = iright = 0
            k = j
            while ileft < llim or iright < rlim:
                if iright >= rlim or (ileft < llim and left[ileft] < right[iright]):
                    a[k] = left[ileft]
                    ileft += 1
                else:
                    a[k] = right[iright]
                    iright += 1
                k += 1
        i *= 2
    return a

n = int(input())
for e in merge_sort_iter([int(sys.stdin.readline().strip()) for _ in range(n)]):
    sys.stdout.write(str(e) + '\n')

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

문제

문제

출처

ICPC

Python3 Merge sort 시간 초과 (Pypy3로는 해결)

Zeta611 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말