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

입력 조건

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

출력 조건

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

 

해결방법

탐색 문제로 여러가지 방법으로 풀 수 있다.

책에서는 이진탐색, 계수탐색, 집합자료형 이용 세가지로 정리해놓았다.

 

제일 먼저 문제를 보고 집합자료형 이용을 할까 생각했지만 앞서 공부한 이진탐색을 이용해보고자 이진탐색 재귀함수를 이용해서 구현하였다.

 

코드 구현

#N개의 숫자가 들어있는 배열 A
#M개의 숫자가 들어있는 배열 B
# A에 B에 있는 데이터와 일치한 것이 있는지 확인

#이진탐색으로 풀어야겠다

#이진탐색 함수
def bineory_search(array, target, start, end) :
    mid=(start+end)//2
    if start>end :
        return None
    else :
        if array[mid]==target :
            return mid
        elif array[mid]<target :
            return bineory_search(array, target, mid+1, end)
        elif array[mid]>target : 
            return bineory_search(array, target, start, mid-1)
    return None

n=int(input())
a=list(map(int, input().split()))
m=int(input())
b=list(map(int, input().split()))
a=sorted(a)

#m의 데이터를 하나씩 이진탐색 함수에 넣고 결과출력
for i in range(m) :
    result=bineory_search(a, b[i], 0, n-1)
    if result==None :
        print("no", end=" ")
    else :
        print("yes", end=" ")

 

난이도는 쉬운 문제이지만 다양한 방법으로 풀어보는 걸 연습하기 좋은 것 같다.