# N개의 정수를 입력 받기
n = int(input())
a = list(map(int, input().split()))
# M개의 정수를 입력 받기
m = int(input())
b = list(map(int, input().split()))
# 출력하기
for word in b:
if word in a:
print(1)
else:
print(0)
시간 초과 이유 : 선형 탐색이 너무 비효율적임.
# N개의 정수를 입력 받기
n = int(input())
a = list(map(int, input().split()))
# M개의 정수를 입력 받기
m = int(input())
b = list(map(int, input().split()))
# 정렬하기
a.sort()
b.sort()
# 출력하기
for word in b:
if word in a:
print(1)
else:
print(0)
시간 초과 이유 2 : 정렬을 하면 탐색시간이 줄어들 것이라 생각했지만 여전히 비효율적임.
# N개의 정수를 입력 받기
n = int(input())
a = list(map(int, input().split()))
# M개의 정수를 입력 받기
m = int(input())
b = list(map(int, input().split()))
# 정렬하기
a.sort()
# 탐색하기
def binary_search(a, alpha):
start = 0
end = len(a) - 1
while end >= start:
mid = (start + end) // 2
target = a[mid]
if alpha == target:
return 1
elif alpha < target:
end = mid - 1
elif alpha > target:
start = mid + 1
return 0
# 출력하기
for alpha in b:
print(binary_search(a, alpha))
해결 방법 : 이진탐색을 이용해 시간 복잡도를 log(n) 으로 줄임