글 읽기 - python으로 합병정렬썼는데 런타임에러가 뜹니다.

rlaeogus890 5년 전 0

예제 출력은 잘되는데 런타임에러가 자꾸 뜹니다.

뭐가 문제인가요?

합병정렬로는 못 푸는 건가요?

import sys
#sys.stdin = open("input.txt","r")

#func lines start
def mergeSort(arr):

    length = len(arr)
    if( length == 1 ):
        return arr
    else:
        arr1 = mergeSort(arr[:int(length/2)])
        arr2 = mergeSort(arr[int(length/2):] )
        arr3 = []
        arr3_adder = arr3.append
        arr1_cursor = 0
        arr2_cursor = 0
        
        #대소 비교하며 채워넣기
        while (arr1_cursor < len(arr1)) and (arr2_cursor < len(arr2)):
            if( arr1[arr1_cursor] <= arr2[arr2_cursor]):
                arr3_adder( arr1[arr1_cursor] )
                arr1_cursor = arr1_cursor + 1
            else:
                arr3_adder( arr2[arr2_cursor] )
                arr2_cursor = arr2_cursor + 1

        #남은거 뒤에 붙여주기
        if(arr1_cursor < len(arr1)):
            arr3.extend(arr1[arr1_cursor:])
        else:
            arr3.extend(arr2[arr2_cursor:])

        return arr3
#func line end


#main

n = int(sys.stdin.readline())
arr = list(map(int, [(sys.stdin.readline()) for i in range(n)] ))

for i in mergeSort(arr):
    print(i)

djm03178 5년 전 0

런타임 에러의 이유는 둘째 치고, 합병 정렬이 절대 의도되지 않은 문제입니다. 메모리 제한도 그렇고, 시간 제한도 그렇습니다.

제가 실험해 본 바로는 Python 3에 합병 정렬을 직접 구현하면 N 제한이 100만 이하인 수 정렬하기 2에서조차 통과가 안 되고, PyPy3를 사용해야 1초 초반대에 통과가 되었습니다. 이 문제는 N 제한이 10배나 되므로 PyPy3로도 10초가 훌쩍 넘을 것이 명백하고, Python 3로는 사실상 불가능하다고 보입니다.

djm03178 5년 전 0

https://www.acmicpc.net/board/...

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

문제

문제

출처

ICPC

python으로 합병정렬썼는데 런타임에러가 뜹니다.

rlaeogus890 5년 전 0

djm03178 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말