[백준 알고리즘] 10815번 숫자 카드. 파이썬(python)

시간초과

반복문으로 하나하나 판별하기엔 범위가 커서 시간초과가 생긴다.

(in 연산은 하나하나 탐색함.)

n=int(input())
cards=list(map(int,input().split()))
m=int(input())
have=list(map(int,input().split()))

for h in have:
    if h in cards:
        print(1,end=' ')
    else:
        print(0,end=' ')

 

 

정답

시간을 최대한 줄이가 위해 이진탐색을 사용한다.

n=int(input())
cards=list(map(int,input().split()))
m=int(input())
have=list(map(int,input().split()))
cards.sort()

def binary_search(start,end,target):
    
    while start<=end:
        mid=(start+end)//2

        if target>cards[mid]:
            start=mid+1
        elif target<cards[mid]:
            end=mid-1
        else:
            return 1
    return 0
        
for h in have:
    print(binary_search(0,n-1,h), end=" ")