[python][백준/BOJ] 10815번 : 숫자 카드

https://www.acmicpc.net/problem/10815

10815번: 숫자 카드

 

✅ 문제 풀이

• 요소들을 여러 개 확인하는 문제는 순차 탐색을 하면 시간초과가 나오는 경우가 대부분이기 때문에
• 이진 탐색을 사용하자!

import sys

n=int(sys.stdin.readline())
a=list(map(int,sys.stdin.readline().split()))
m=int(sys.stdin.readline())
b=list(map(int,sys.stdin.readline().split()))

a.sort()

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

        if arr[mid]==target:
            return mid
        elif arr[mid]>target:
            end=mid-1
        else:
            start=mid+1
    return None

for i in range(m):
    if binary_search(a,b[i],0,n-1) is not None:
        print("1",end=' ')
    else:
        print("0",end=' ')