글 읽기 - 파이썬 시간초과(제발 도와주세요)

skan4342 3년 전 0

이진탐색으로 풀었습니다.

pypy3도 쓰고 빠른 입출력도 했는데 시간초과가 나와서 너무 슬픕니다.

왜 시간 초과 나오는지 알려주시면 감사하겠습니다.

import sys
a = int(sys.stdin.readline())
a1 = []
a1 = list(map(int,sys.stdin.readline().split()))

b1 = int(sys.stdin.readline())
b = []
b = list(map(int,sys.stdin.readline().split()))

a1.sort()

def binary (list,key):
    if len(list) == 1:
      if list[0] == key:
        return 1
      else:
        return 0
    mid = len(list) // 2
    if key == list[mid]:
      return 1
    elif key > list[mid]:
      return binary(list[mid:],key)
    else:
      return binary(list[:mid],key)
   
for i in b: 
  print(binary(a1,i))

shg9411 3년 전 1

slicing, 재귀를 사용하지 말고 while문으로 이분탐색 작성해보세요.

넉넉하게 통과하네요.

skan4342 3년 전 0

말씀하신대로 해보니까 통과했습니다.

왜 재귀는 안된건지 설명해주시면 감사하겠습니다

dietomorrow 3년 전 0

slicing에 시간이 소모됩니다.

skan4342 3년 전 0

설명감사합니다~

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

문제

문제

출처

ICPC

파이썬 시간초과(제발 도와주세요)

skan4342 3년 전 0

shg9411 3년 전 1

skan4342 3년 전 0

dietomorrow 3년 전 0

skan4342 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말