[이코테] 7-2 부품 찾기(이진탐색)

정리내용은 [이것이 취업을 위한 코딩 테스트다 with 파이썬] 책을 기반으로 작성하였습니다.

이것이 취업을 위한 코딩 테스트다 with 파이썬 - 교보문고

---

난이도 중하 | 풀이시간 30분 | 시간제한 1초 | 메모리제한 128MB

 

문제

동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개의 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자.

예를 들어 가게의 부품이 총 5개일 때 부품 번호가 다음과 같다고 하자.

N=5
[8, 3, 7, 9, 2]

 

손님은 총 3개의 부품이 있는지 확인 요청했는데 부품 번호는 다음과 같다.

M=3[5,7,9]

 

이때 손님이 요청한 부품 번호의 순서대로 부품을 확인해 부품이 있으면 yes를, 없으면 no를 출력한다. 

 

입력 조건

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

 

출력 조건

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

 

코드 구현

import sys

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if array[mid] == target:
            return mid

        elif target < array[mid]:  ## 중간점보다 크면 앞쪽을 찾아야된다!
            end = mid - 1
        else:
            start = mid + 1
    return None


N=int(sys.stdin.readline())
tool_list=list(map(int,sys.stdin.readline().split(" ")))
M=int(sys.stdin.readline())
check_list=list(map(int,sys.stdin.readline().split(" ")))

tool_list.sort()
print(tool_list)
for c in check_list:
    val=binary_search(tool_list,c,0,N-1)
    if val!=None:
        print("Yes")
    else:
        print("No")

매장에 있는 데이터를 우선 sort로 정렬한 후 이진탐색으로 해당 값이 있는지 없는지 찾으면 된다.