이것이 코딩테스트다 부품찾기 (Python)

문제 링크

동빈이네 전자 매장에 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호.

어느날 손님이 M개 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 대를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이 때 가게 안에 부품이 모두 있는지를 확인하는 프로그램을 작성하시오.

부품 개수 : 1 ≤ N ≤ 1,000,000

문의한 부품 : 1 ≤ M ≤ 1,000,000

---

Test Case

입력
5
8 3 7 9 2
3
5 7 9

출력
no yes yes

---

문제 풀이

이진탐색 알고리즘으로도 풀 수 있고, 계수정렬로도 풀 수 있는데 set 자료구조로도 풀수 있는데 set 개념 기억해두려고 포스팅

---

Source Code

import sys
input = sys.stdin.readline

n = int(input())
bupum = list(map(int, input().split()))

m = int(input())
sonnim = list(map(int, input().split()))

def binary_search(arr,target,start,end):
    if start > end :
        return False
    mid = (start+end) // 2
    
    
    if arr[mid] > target :
        return binary_search(arr,target,start,mid-1)
    elif arr[mid] < target :
        return binary_search(arr,target,mid+1,end)
    else :
        return True
    
bupum.sort()

for i in sonnim:
    result = binary_search(bupum,i,0,n-1)
    if result == True:
        print("yes")
    else :
        print("no")

 

import sys
input = sys.stdin.readline

n = int(input())
bupum = set(map(int, input().split()))

m = int(input())
sonnim = list(map(int, input().split()))

for i in sonnim:
    if i in bupum :
        print("yes")
    else :
        print("no")