[백준][Python] 1920번 수 찾기

1920번: 수 찾기

 

코드

def find(num):
	f = 0
	e = n-1
	while f <= e:
		mid = (f+e)//2
		if num == n_list[mid]:
			return 1
		elif num > n_list[mid]:
			f = mid+1
		else:
			e = mid-1
	return 0
n = int(input())
n_list = list(map(int,input().split()))
n_list.sort()
m = int(input())
m_list = list(map(int,input().split()))

for i in m_list:
	print(find(i))

 

설명

처음에 in 을 이용하여 리스트 탐색을 해서 풀었더니 시간 초과가 났다. 그래서 이진  탐색 방법을 사용해서 리스트에 해당 값이 있는지 확인을 했다.

 

검색을 해보니 리스트 탐색은 O(n)의 시간 복잡도를 가지지만 set 탐색은 O(1)의 시간 복잡도를 가져 훨씬 빠른 것을 알 수 있었다. 파이썬에서 set가 해시 테이블로 구현되어서 그렇다고 한다.

따라서 n_list를 set으로 받으면 in을 이용하여 탐색을 하더라도 시간 초과가 나지 않는다.