[백준 1920번] 수 찾기

import sys
input = sys.stdin.readline

n = int(input())
# List의 in은 평균 시간복잡도가 O(N)이고, Set의 in은 평균 시간복잡도가 O(1)이다
# (Set은 해쉬 테이블을 사용하기 때문)
set_n = set(map(int,input().split()))

m = int(input())

array_m = list(map(int,input().split()))

for i in array_m:
  if i in set_n:
    print(1)
  else:
    print(0)

이번 문제는 이진 탐색을 사용하지 않고 풀이하려고 했었는데, n개의 데이터가 들어있는 리스트(List)로 저장하고 in 연산자를 사용하니 시간초과가 발생했다.

 

따라서 이를 해결하기 위해 in 연산자의 시간 복잡도가 O(1)인 집합(Set) 자료형을 사용하였다 :)