[#알고리즘/이진 탐색/[이코테]부품 찾기(python)]

Question

어떤 전자 매장에는 정수 번호를 가지는 부품이 N개 있다. 어느 날 손님이 M개 종류의 부품을 대량으로 구매하겠다며 견적서를 요청했다. 직원은 손님이 문의한 부품 M개 종류를 모두 확인해 견적서를 작성하려 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성하라. 부품이 있으면 yes, 없으면 no를 출력하라.

Solution

먼저 매장 내 N개의 부품을 번호 기준으로 오름차순 정렬을 한다. 그 이후 M개의 찾고자 하는 부품이 각각 매장에 존재하는지 검사한다.
data(부품들)가 정렬되어 있으므로 이진 탐색을 수행하여 문제를 해결한다.

Code

import sys

def binary_search(array, target, start, end) :
    if start > end :
        return None
    mid = (start + end) // 2
    if array[mid] == target:
        return mid
    elif array[mid] > target:
        return binary_search(array, target, start, mid - 1)
    else :
        return binary_search(array, target, mid + 1, end)
    
n = int(input())
array = list(map(int, sys.stdin.readline().split()))

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

for i in item :
	# 해당 부품이 존재하는지 확인
    x = binary_search(array, i, 0, n-1) 
    if x != None :
        print("yes", end = '')
    else : 
        print("no", end = '')