부품 찾기

p. 197

 

방법 1. 이진 탐색

def binary_search(array, target, start, end):
  if start>end:
    return None
  middle=(start+end)//2
  if array[middle]==target:
    return middle
  elif array[middle]<target:
    start=middle+1
  else:
    end=middle-1
  return binary_search(array, target, start, end)

n=int(input())
n_r=list(map(int, input().split()))
n_r.sort()

m=int(input())
m_r=list(map(int, input().split()))

for i in m_r:
  if binary_search(n_r, i, 0, len(n_r)) !=None:
    print("yes", end=' ')
  else:
    print("no", end=' ')

 

방법 2. 계수 정렬

n=int(input())
n_r=list(map(int, input().split()))
n_list=[0]*(max(n_r)+1)
for i in n_r:
  n_list[i]+=1

m=int(input())
m_r=list(map(int, input().split()))

for i in m_r:
  if n_list[i]!=0:
    print("yes", end=' ')
  else:
    print("no", end=' ')

 

방법 3. set 사용

n=int(input())
n_r=set(map(int, input().split()))

m=int(input())
m_r=list(map(int, input().split()))

for i in m_r:
  if i in n_r:
    print("yes", end=' ')
  else:
    print("no", end=' ')