백준 1920

풀이

처음에는 count 함수를 사용해서 코드를 제출하였으나 시간 초과로 문제 풀이에 실패하였다.

빠른 탐색 코드를 원하는 것 같아, 이분 탐색으로 시도하였다.

 

import sys
input = sys.stdin.readline

N = int(input().rstrip())
N_nums = list(map(int, input().split()))
M = int(input().rstrip())
M_nums = list(map(int, input().split()))

# 이분 탐색을 위해 오름차순 정렬
N_nums.sort()

def bin_search(start, mid, end, goal):
	# start와 end가 같아도 되는 경우는 존재, 그러나 아래의 경우는 불가
	if start > end:
    	return -1
        
    elif N_nums[mid] > goal:
    	end = mid - 1
        return bin_search(start, int((start + end) / 2)), end, goal)
        
    elif N_nums[mid] == goal:
    	return mid
        
    elif N_nums[mid] < goal:
    	start = mid + 1
        return bin_search(start, int((start + end) / 2)), end, goal)

for i in M_nums:
	if bin_search(0, int(len(N_nums) / 2), len(N_nums) - 1, i) == -1
    	print(0)
    else:
    	print(1)

 

References

---

https://www.youtube.com/watch?v=94RC-DsGMLo&t=298s