글 읽기 - python에서 merge sort로 했을 때 에러

sula50 4년 전 0

처음에 아래쪽에 주석 처리된 코드로 했는데 시간초과가 나서,

배열 크기같은 거 정해놓으면 조금이나마 빨라질까 해서 위에것으로 바꿨어요.

그런데 런타임에러가 나요.

제가 쓰는 python 3의 version 은 3.7.3이고

이 shell 에서는 해당 코드가 문제 없이 돌아가는데 사이트에서는 안 되는 이유를 알고싶어요.

만약 다시 시간초과가 났다면,

'내가 이런 방식을 처음 접해서 미숙하구나. 좀더 low level에서 구현하는 걸 알아봐야겠다.'

하겠는데

이건 되기도 하고 안 되기도 하니까 어디가 문제인건질 모르겠어요.

import ctypes

def m(arr1, arr2):
    sortedArr = ((len(arr1)+len(arr2))*ctypes.py_object)()
    i = j = k = 0
    while i != len(arr1) and j != len(arr2):
        if arr1[i] >= arr2[j]:
            sortedArr[k] = arr2[j]
            k += 1
            j += 1
        else:
            sortedArr[k] = arr1[i]
            k += 1
            i += 1
    for l in range(i, len(arr1)):
        sortedArr[k] = arr1[l]
        k += 1
    for l in range(j, len(arr2)):
        sortedArr[k] = arr2[l]
        k += 1
    return sortedArr[:]

def mSort(L):
    if len(L) == 0:
        return
    tempList = [None] * (len(L) * 2 - 1)
    for i in range(len(L)):
        tempList[i] = (1 * ctypes.py_object)()
        tempList[i][0] = L[i]
    
    p = len(L)
    i = 0
    while p != len(tempList):
        tempList[p] = ((len(tempList[i]) + len(tempList[i + 1])) * ctypes.py_object)()
        tempList[p] = m(tempList[i], tempList[i + 1])
        p += 1
        i += 2
        
    
    L[:] = tempList[-1][:]

N = int(input())
nums = [0] * N

for i in range(N):
    nums[i] = int(input())
mSort(nums)
for n in nums:
    print(n)
"""    
###
    
def m(L1, L2):
    sortedList = []
    i = j = 0
    while i != len(L1) and j != len(L2):
        if L1[i] >= L2[j]:
            sortedList.append(L2[j])
            j += 1
        else:
            sortedList.append(L1[i])
            i += 1
    for k in range(i, len(L1)):
        sortedList.append(L1[i])
    for k in range(j, len(L2)):
        sortedList.append(L2[j])
    return sortedList

def mSort(L):
    templ = []
    for n in L:
        templ.append([n])
    i = 0
    while i + 1 != len(templ):
        templ.append(m(templ[i], templ[i + 1]))
        i += 2
    if len(templ) != 0:
        L[:] = templ[-1][:]
        
N = int(input())
nums = list()
for i in range(N):
    nums.append(int(input()))
mSort(nums)
for n in nums:
    print(n)
"""

happiness96 4년 전 1

입력을 받을 때 생기는 문제인 것 같아요~

input 함수보다 더 빨리 입력을 받는 방법이 있어요.

input 대신 sys.stdin.readline 함수를 사용해보세요.

sula50 4년 전 0

입력 부분을 수정해도 시간초과가 나오네요.

또, 같은 방식을 다른 언어로 취해도 느린게 전반적으로 문제가 있는 것으로 여겨집니다, 어떤 식으로든.

지금 저로서는 알기 어렵지만요...ㅠ

다른 방식을 생각해보는 편이 좋아 보여서 강해지러 가야겠습니다.

답글 감사합니다.

djm03178 4년 전 0

파이썬 3는 그냥 너무 느린 언어입니다. 그 뿐입니다. C 계열의 언어에 비해 최소 수십에서 백배 수준까지 느리기 때문에 BOJ의 시간 보너스로 상쇄하기에는 어림도 없습니다. 내장 함수가 아닌 직접 구현한 코드로 백만log백만은 파이썬 3로 시간 내에 풀기에는 너무 큽니다. 대신에 PyPy3를 사용하면 훨씬 빠릅니다.

가장 최근에 시간 초과를 받으신 코드를 PyPy3로 제출하면 정답을 받습니다. http://boj.kr/666af9e55af64099...

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

문제

문제

출처

ICPC

python에서 merge sort로 했을 때 에러

sula50 4년 전 0

happiness96 4년 전 1

sula50 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말