[Python] 백준 1920번

1920번. 수 찾기 (silver 4)

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

 

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다.

 

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

 

 

이 문제는 이진 탐색을 이용하면 빨리 답을 구할 수 있는 문제이다.

 

존재하는지 알아내고 싶은 m개의 수를 key로 두고 key값을 찾으면 되는 문제이다.

binary_search라는 함수를 정의해서 이를 사용해주었다.

함수의 인자로 배열, Key값, 시작값에 해당하는 start, 끝 값에 해당하는 end를 받아주었고,

first가 end보다 크면 false를 반환해서 후에 for문에서 0이 반환되게 해주었고,

그 외의 경우 mid값에 (start+end)//2를 저장하고 num[mid]값과 key값을 비교해서 같다면 True를 반환해서 후의 for문에서 1이 출력되도록 해주었다.

num[mid]의 값이 key값보다 크다면 binary_search를 재귀호출 해주어서 다시 수행되게 해주었는데, 이때 end의 값을 mid-1로 바꿔주었다. 그리고 num[mid] 값이 key값보다 작은 경우에는 재귀호출을 할 때 start의 값을 mid+1로 설정해주었다.

m개의 수들이 담긴 m_list의 원소를 for문을 돌려서 1또는 0을 출력해주면 된다.

 

 

 

# 이진 탐색
def binary_search(num, key, start, end):
    if start > end:
        return False
    mid = (start + end) // 2  # 중간 값
    if num[mid] == key:
        return True
    elif num[mid] > key:
        return binary_search(num, key, start, mid-1)
    else:
        return binary_search(num, key, mid+1, end)

num = int(input())
n_list = list(map(int, input().split()))
m = int(input())
m_list = list(map(int, input().split()))
n_list = sorted(n_list)

for m in m_list:
    if binary_search(n_list, m, 0, num-1):
        print(1)
    else:
        print(0)