글 읽기 - 파이썬 시간초과 메모리 초과를 벗어나지 못합니다

dddolmaeng 2년 전 0

파이썬은 시간초과 PYPY로는 메모리 초과가 발생합니다

코드에 대해서 간단하게 설명하자면 각각의 tree 노드에는 sort된 배열이 들어가고

배열 a[i....j]를 중복되지 않은 leaf를 가진 트리들의 노드들을 merge sort 해주어서 그 중에 k번쨰 숫자를 출력하는 코드입니다.

init함수는 트리 설정(node는 배열)

merge함수는 이미 정렬된 list 2개를 merge sort하는 코드

find_arr함수는 합쳐야될 노드를 찾아주는 함수입니다.

파이썬은 비효율적이라 시간초과가 나는 것 같고 PYPY로는 tree가 array를 각각 인수로 가지고 있어서 메모리 초과가 나는 것 같은데

트리를 사용하고 파이썬으로 이 문제를 어떻게 해결해야될지 막막해서 질문드립니다.

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def init(node, start, end):
  if start == end:
    tree[node] = [arr[start]]
    return
  
  mid = (start+end)//2
  
  init(node*2, start, mid)
  init(node*2+1, mid+1, end)
  tree[node] = merge(tree[node*2],tree[node*2+1])
  return
  

def merge(left_arr, right_arr):
  if len(left_arr) == 0 or len(right_arr) == 0:
    return left_arr+right_arr

  arr = []
  i, j = 0, 0
  while i < len(left_arr) and j < len(right_arr):
    if left_arr[i] <= right_arr[j]:
      arr.append(left_arr[i])
      i+=1
    else:
      arr.append(right_arr[j])
      j+=1
  
  if i == len(left_arr):
    for ind in range(j, len(right_arr)):
      arr.append(right_arr[ind])
    
  else:
    for ind in range(i, len(left_arr)):
      arr.append(left_arr[ind])
  
  return arr


def find_arr(node, start, end, left, right):
  if right < start or end < left:
    return []
  
  if left <= start and end <= right:
    return tree[node]
  
  mid = (start+end)//2

  left_arr = find_arr(node*2, start, mid, left, right)
  right_arr = find_arr(node*2+1, mid+1, end, left, right)

  return merge(left_arr, right_arr)



n, m = map(int, input().split())
arr = list(map(int, input().split()))
tree = [[] for _ in range(3*n)]
init(1, 0 , n-1)
for _ in range(m):
  a, b, c = map(int, input().split())
  left = a-1
  right = b-1
  kth = c-1

  A = find_arr(1, 0, n-1, left, right)
  print(A[kth])

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

문제

문제

출처

ICPC

파이썬 시간초과 메모리 초과를 벗어나지 못합니다

dddolmaeng 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말