글 읽기 - [python] 시간초과 왜나는 거죠?.

ujtel1234 2년 전 0

가지고 있는 숫자개수 n, 트라이 개수 m이면 시간복잡도 O( n log(n) + m log(n) ) 나오는데 시간초과가뜨네요,,,

어차피 이진탐색 쓰려면 한번은 정렬해야될거같은데.. 여기서 어떻게 시간 줄여야 하죠?

import sys

input = sys.stdin.readline

class Bi_searh:

    def __init__(self,num_list:list,num_lenth:int) -> None:
        self.num_list = num_list
        self.lenth = num_lenth
        #시간복잡도 O(n log(n))
        self.num_list.sort()

    def search(self,key:int):

        def _search(num_list:list,key:int,lenth:int):

            mid = lenth // 2

            if lenth == 1 :
                if num_list[0] == key:
                    return True
                else:
                    return False
            elif lenth == 0:
                return False

            if num_list[mid] == key:
                return True
            else:

                if num_list[mid] > key:
                    return _search(num_list[:mid],key,mid)
                else:
                    return _search(num_list[mid+1:],key,lenth-mid-1)

        return _search(self.num_list,key,self.lenth)


def test():

    a1 = Bi_searh([6,3,2,10,-10])

    test_num = [10,9,-5,2,3,4,5,-10]

    for i in test_num:
        print(a1.search(i))


def main():

    num_lenth = int(input())

    num_list = list(map(int,input().split(" ")))

    test_lenth = int(input())

    test_nums = list(map(int,input().split(" ")))

    tester = Bi_searh(num_list,num_lenth)


    for num in test_nums:

        if tester.search(num):
            print(1,end=" ")
        else:
            print(0,end=" ")


if __name__ == "__main__":

    main()