백준 10815. 숫자 카드

다음 단계인 집합과 맵.

처음에 문제를 봤을 때는 왜 집합을 이용하는지 이해하지 못했다. 문제의 조건에서도 카드의 숫자가 중복되는 일은 없다고 하는데 굳이 집합을 써야 하나..?

그래서 리스트와 in list 를 활용한 코드를 제출했더니 날 반기는 시간 초과 ㅋㅋㅋㅋㅋ

 

약간의 구글링 후에 in을 쓸 때는 집합이 리스트보다 시간 복잡도가 훨씬 낮다는 점을 알아냈다. 해쉬 맵을 쓰기 때문에 (이는 후에 포스팅할 거리) 시간 복잡도가 O(1)이고, 리스트의 경우에는 모든 원소를 뒤져야 하기 때문에 시간 복잡도가 O(n)이다. 그래서 집합을 쓰면 쉽게 풀림.

 

import sys

n = int(sys.stdin.readline())
cards = set(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
to_find = list(map(int, sys.stdin.readline().split()))
for i in to_find :
	if i in cards:
		print(1)
	else:
		print(0)
print()