백준 수찾기(1920번) 파이썬 풀이

전체 코드

# 수 찾기
N=int(input())
A=list(map(int,input().split()))
M=int(input())
B=list(map(int,input().split()))

def is_there(min_idx, max_idx, array, num):    
    
    middle_idx=(min_idx+max_idx)//2

    if (array[middle_idx]==num or array[max_idx]==num) or array[min_idx]==num:
        print(1)
        return

    if max_idx-min_idx==1:
        print(0)
        return

    elif array[middle_idx]<num:
        return is_there(middle_idx, max_idx, array, num)
    elif array[middle_idx]>num: 
        return is_there(min_idx, middle_idx, array, num)

A.sort()
min_=min(A)
max_=max(A)
for i in B:
    if min_<=i and max_>=i:
        result=is_there(0,len(A)-1,A,i)
    else:
        print(0)

https://www.acmicpc.net/problem/1920

---

문제

두번째 입력을 리스트로 받아 A로 저장, 네번째 입력을 리스트로 받아 B로 각각 저장했다

문제는 B의 각요소가 A에 존재하면 1 존재하지않으면 0을 출력하도록 요구한다

 

해결

1. 이분탐색을 적용하기위해 A를 정렬한다

2. 최대값 최소값 범위이내에 i(B의 각 요소)가 있는지 확인한다 범위안에 있는게 확인되었을경우 재귀함수를 이용한 이분탐색을 시작한다