부품 찾기

💻 입력 조건

• 첫째 줄에 정수 N이 주어진다. (1 <= N <= 1,000,000)
• 둘째 줄에는 공백으로 구분하여 N개의 정수가 주어진다. 이때 정수는 1보다 크고 1,000,000 이하이다.
• 셋째 줄에는 정수 M이 주어진다. (1 <= M <= 100,000)
• 넷째 줄에는 공백으로 구분하여 M개의 정수가 주어진다. 이때 정수는 1보다 크고 1,000,000 이다히다.

💻 출력 조건

• 첫째 줄에 공백으로 구분하여 각 부품이 존재하면 yes, 없으면 no를 출력한다.

💻 입력 예시

5
8 3 7 9 2
3
5 7 9

💻 출력 예시

no yes yes

📖 문제 해결
최대 1,000,000개의 매우 많은 정수를 입력받아야 할 수도 있기 때문에 이진 탐색 알고리즘을 이용하였습니다. 이진 탐색 알고리즘을 이용하기 위하여 가게에 있는 부품들이 담긴 리스트를 우선 정렬한 후, 손님께서 요구한 부품 리스트의 순서대로 확인하며 이진 탐색 결과 가게 내에 부품이 있으면 yes를, 없으면 no를 출력할 수 있도록 코드를 작성하였습니다.

# N을 입력 받기
n = int(input())

# N개의 정수 입력받기
n_list = list(map(int,input().split()))

# M을 입력 받기
m = int(input())

# M개의 정수 입력 받기 
m_list = list(map(int,input().split()))

# 이진 탐색 함수
def binary_search(array, target, start, end):
    
    if start > end:
        return None
    
    mid = (start + end) // 2
    
    if array[mid] == target:
        return mid + 1
    
    elif array[mid] > target:
        return binary_search(array, target, start, mid - 1)
    
    else:
        return binary_search(array, target, mid + 1, end)
    
# 이진 탐색 알고리즘을 이용하기 위해 n_list 정렬
n_list.sort()

# 이진 탐색을 이용하여 부품을 찾아 있으면 'yes'를, 없으면 'no'를 출력
for item in m_list:
    if binary_search(n_list, item, 0, len(n_list)-1) != None:
        print('yes', end = ' ')
    else:
        print('no', end = ' ')

참고로, M개의 부품을 찾는 과정에서 최악의 경우 시간 복잡도 O(M x logN) 의 연산이 필요하고 N개의 부품을 정렬하는 과정에서 시간 복잡도 O(N x logN) 의 연산이 필요합니다. 따라서 결과적으로 이진 탐색을 사용하는 문제 풀이 방법의 경우 시간 복잡도는 O((M + N) x logN) 입니다.