[백준][Python] 10815번 숫자 카드

10815번: 숫자 카드

 

시간초과 코드

n = int(input())
n_list = list(map(int,input().split()))
m = int(input())
m_list = list(map(int,input().split()))

for i in m_list:
	if i in n_list:
		print(1,end=" ")
	else:
		print(0,end=" ")

in을 이용해서 해당 숫자가 리스트에 있는지 확인을 하는 코드를 작성했는데 시간 초과가 떴다.

하나하나 순회하기 때문에 데이터의 크기만큼 시간 복잡도를 갖게 되기 때문이다 ( 시간 복잡도 : O(n) )

 

코드

def binsearch(num):
	global s, e
	while s <= e:
		mid = (s+e)//2
		if n_list[mid] < num:
			s = mid+1
		elif n_list[mid] > num:
			e = mid-1
		else:
			return True
	return False

n = int(input())
n_list = list(map(int,input().split()))
m = int(input())
m_list = list(map(int,input().split()))
n_list.sort()
for i in m_list:
	s = 0
	e = n-1
	if binsearch(i):
		print(1,end=" ")
	else:
		print(0,end=" ")

이진탐색을 이용하여 다시 풀었다. ( 시간 복잡도 : O(logN) )