백준 | 1920 수 찾기

import sys

n = int(input())
a = set(map(int, sys.stdin.readline().split()))  # 리스트를 집합 set으로 변환

m = int(input())
m_num = list(map(int, sys.stdin.readline().split()))

# 각 숫자에 대해 집합에서 검색
for num in m_num:
    if num in a:
        print(1)
    else:
        print(0)


# 오답 (시간 초과)
import sys

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

m = int(input())
m_num = list(map(int, sys.stdin.readline().split()))

for num in m_num:
    if num in a:
        print(1)
    else:
        print(0)

 

* 시간 초과 이유 : list(a)에 in 연산자를 사용해서 > 최악의 경우 O(n*m)의 시간 복잡도 발생

  n, m이 커질수록 시간 초과되기 때문에 list(a)를 set(a)로 변환

>> in 연산자를 사용할 때는 집합(set)을 사용하기

  (해시 테이블 기반이라 평균 O(1)의 시간 복잡도, list는 O(n)의 시간 복잡도 )

 

 

• 집합 (set): in 연산자는 평균적으로 O(1)의 시간 복잡도를 가집니다. 이는 해시 테이블을 사용하여 요소를 빠르게 찾을 수 있기 때문입니다.
• 리스트 (list): in 연산자는 O(n)의 시간 복잡도를 가집니다. 리스트의 요소를 처음부터 끝까지 순차적으로 검색하기 때문에 요소의 수가 많을수록 시간이 많이 걸립니다.