글 읽기 - Python3 시간초과뜹니다ㅠㅠ

ehe1021 6년 전 0

병합정렬로 문제를 풀었는데 시간초과가 뜹니다..

뭐가 문제일까요..ㅠㅠ

def merge( left , right ) :
          olist = []
          while left != [] and right !=[] :
                    if left[0] > right[0] :
                              olist += [ right[0] ]
                              right.remove( right[0] )
                    else :
                              olist += [ left[0] ]
                              left.remove( left[0] )
          if left == []:
                      return olist + right
          else:
                      return olist + left



def divide( list ):
          cnt = len(list)
          mid = cnt // 2
          if cnt > 1 :
                    return merge ( divide( list[:mid] ) , divide( list[mid:] ) )
          else:
                    return merge ( list[:mid] , list[mid:] )
N = int(input())
lists = []

for _ in range(N):
    num = input()
    lists += [ num ]
print( divide( lists ) )

sait2000 6년 전 0

질문에 문제 번호가 없네요;; 제 느낌에는 merge에서 remove할 때마다 다른 모든 원소가 한 칸씩 이동하니까 merge가 O(n^2)이어서 그런 것 같아요.

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

문제

문제

출처

ICPC

Python3 시간초과뜹니다ㅠㅠ

ehe1021 6년 전 0

sait2000 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말