글 읽기 - 파이썬 merge sort(병합 정렬) 시간초과 관해서 도와주십쇼..

kalim55555 5년 전 0

파이참이나 다른 에디터에서는 문제 없이 돌아가는 데 백준 채점에서만 시간 초과가 뜹니다.

input도 sys.stdin.readline()으로 바꾸었고, 시간을 많이 줄여보려고 했는데 역시 파이썬은 느리더군요

혹시 머가 문제인지 알려주실 수 있나요? 시간이 어디서 오래 걸렸고.. 이 문제는 병합 정렬로 풀 수 없는 문제인지

풀 수 있다면 그 방법이 무엇인지 ... 부탁드립니다~

import sys

def Mergesort(list):
    if len(list) <= 1:
        return list
    mid = len(list) // 2 
    left = list[:mid]
    right = list[mid:]
    
    next_left = Mergesort(left) 
    next_right = Mergesort(right)
    
    return Merge(next_left, next_right)
    
def Merge(left, right):
    i =0
    j =0
    sorted_list = []
    while (i < len(left)) & (j < len(right)):
        if left[i] < right[j]:
            sorted_list.append(left[i])
            i +=1
        else:
            sorted_list.append(right[j])
            j +=1
    while i < len(left):
        sorted_list.append(left[i])
        i +=1
    while j < len(right):
        sorted_list.append(right[j])
        j +=1
    return sorted_list

num = int(sys.stdin.readline())

list = []

for i in range(num):
    list.append(int(sys.stdin.readline()))
    
final = Mergesort(list)    
    
for i in final:
    print(i)

jh05013 5년 전 1

Pypy3로 제출해 보세요. 같은 문법인데 훨씬 빠릅니다.

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

문제

문제

출처

ICPC

파이썬 merge sort(병합 정렬) 시간초과 관해서 도와주십쇼..

kalim55555 5년 전 0

jh05013 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말