이것이 코딩테스트다 - 12일차

주제

binary search

문제

전자 매장에는 부품 N개가 있다. 각 부품은 고유한 정수형태의 번호가 존재한다.

손님이 M개 종류의 부품을 대량으로 구매하겠다며 당일날 견적서를 요청했다.

손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다.

이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성하자

부품이 존재한다면 yes로 부품이 존재하지 않는다면 no로 출력하라

예시

N = 5 # 전자 매장 부품 개수
[8, 3, 7, 9, 2] # 전자 매장 부품 고유 번호

M = 3 # 손님이 찾는 부품 개수
[5, 7, 9] # 손님이 찾는 부품 고유 번호

조건

첫째 줄에 정수 N이 주어진다. (1 <= N <= 1,000,000)

둘째 줄에는 공백으로 구분하여 N개의 정수가 주어진다. (1 < 정수 <= 1,000,000)

셋째 줄에는 정수 M이 주어진다. (1 <= M <= 100,000)

넷째 줄에는 공백으로 구분하여 M개의 정수가 주어진다. (1 < 정수 <= 1,000,000)

풀이 방법

만약 N개의 부품을 정렬하고 M개를 하나하나씩 찾는다면 O(1,000,000 * 100,000) 만큼의 시간이 소요된다. = (반복문 사용시)

binary search를 사용하게 되면 O(MlogN) = O(100,000log1,000,000) 만큼의 시간이 소요되어 대략 200만의 연산이 소요된다.

1. 입력을 받는다.
2. binary search를 사용한다.
3. 만약 None일 경우 no, None이 아닐 경우 yes를 출력한다.

N = int(input())
part_list = list(map(int, input().split()))

M = int(input())
find_part_list = list(map(int, input().split()))

part_list.sort()

def binary_search(start, end, part_list, target):
    if start >= end:
        return None

    mid = (start + end) // 2

    if part_list[mid] == target:
        return part_list[mid]
    elif part_list[mid] > target: # 부품 리스트의 중앙값보다 고객이 찾고자하는 값이 더 작은 경우 데이터는 왼쪽에 존재함
        return binary_search(start, mid - 1, part_list, target)
    elif part_list[mid] < target: # 부품 리스트의 중앙값보다 고객이 찾고하자는 값이 더 큰 경우 데이터는 오른쪽에 존재함
        return binary_search(mid + 1, end, part_list, target)

for target in find_part_list:
    result = binary_search(0, len(part_list), part_list, target)

    if result == None:
        print('no', end=' ')
    else:
        print('yes', end=' ')