[백준/파이썬] 10815번 숫자 카드

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

10815번: 숫자 카드

각 배열을 처음부터 끝까지 탐색하면 시간초과가 나도록 유도하는 문제이다.

O(log n)의 시간복잡도를 가지는 이분탐색을 활용해야한다.

상근이가 가지고 있는 숫자카드가 비교할 배열보다 작으니까, 숫자카드에서 수를 하나 뽑아서 상근이의 숫자카드 목록에 있는지 찾아주면 된다.

import sys

def binary_search(arr, num,left,right):
    
    while left <= right:
        mid = int((left + right) /2)
        
        if arr[mid]==num:
            return True
        
        elif arr[mid] < num:
            left = mid +1
        else :
            right = mid -1
    
    return False


n = int(input())
card  =list(map(int, sys.stdin.readline().split()))

m = int(input())
cmp  = list(map(int, sys.stdin.readline().split()))
card = sorted(card)

for i in cmp:
    if binary_search(card, i,0,n-):
        print(1, end= ' ')
    else:
        print(0, end=' ')