[이것이 코딩 테스트다] 부품 찾기

🔒 문제

 전자 매장에는 부품이 N개 있고, 각 부품은 정수 형태의 고유한 번호가 있다. 부품 M개 종류가 모두 있는지 확인하는 프로그램을 작성해보자.

입력

5
8 3 7 9 2
3
5 7 9

출력

no yes yes

✅ 해설

• 손님이 원하는 부품이 매장에 있는지 [탐색하는 알고리즘]을 짜는 게 관건
  • 매장의 부품을 오름차순으로 정렬한 뒤, 이진 탐색
• 손님이 요구하는 부품을 리스트로 받은 뒤, 리스트에서 원소를 꺼내오며 각각 이진탐색을 시행

for 부품 in 손님_부품_리스트:
	check = 이진_탐색_함수_실행_후_리턴값
    if check:
    	print("yes")
    else:
    	print("no")

💻 코드

# 매장
n = int(input())
store = list(map(int, input().split()))

# 손님
m = int(input())
customer = list(map(int, input().split()))

# 매장 부품 오름차순 정렬
store.sort()

# 이진 탐색 알고리즘
def search(array, target, start, end):
    # 시작과 끝이 역전되는 순간, 찾는 값이 없음을 의미
    if start > end:
        return False

    # mid는 시작과 끝의 중간 인덱스
    mid = (start + end) // 2

    # 중간값이 목표값과 같다면
    if array[mid] == target:
        return True

    # 중간값이 목표값보다 작다면
    elif target > array[mid]:
        # 중간 이후 값들을 재탐색
        return search(array, target, mid+1, end)

    else:
        # 중간 이전 값들을 재탐색
        return search(array, target, start, mid-1)

# 손님이 요구하는 부품을 하나씩 탐색
for target in customer:
    check = search(store, target, 0, n-1)
    if search(store, target, 0, n-1):
        print("yes", end=' ')
    else:
        print("no", end=' ')