[Python3] 백준(Baekjoon) 숫자카드 10815

문제 :

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

접근 :

제한 숫자가 크기 때문에 시간 초과가 어떻게 해도 난다.

이진 탐색을 활용해서 문제를 풀었다.

풀이 :

import sys

def binary_search (array, target, start, end):
    while start <= end :
        mid = (start + end) //2 
        if array[mid] == target :
            return mid
        
        elif array[mid] > target :
            end = mid - 1
        
        else :
            start = mid + 1
    return None

N = int(input())
arr = sorted(list(map(int, sys.stdin.readline().split())))
M = int(input())
card = list(map(int, sys.stdin.readline().split()))
ans = []

for i in card :
    result = binary_search(arr, i, 0, len(arr)-1)
    if result == None:
        ans.append(0)
    else :
        ans.append(1)

print(*ans, sep=' ')