[Python/파이썬] 백준 1920번 수 찾기

문제

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을 출력한다.

코드

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

n = int(input())
arr1 = list(map(int, input().split()))
m = int(input())
arr2 = list(map(int, input().split()))

arr1.sort()

for i in arr2:
    if binary_search(arr1, i, 0, n - 1):
        print("1")
    else:
        print("0")

처음에는 

for i in arr2:
    if i in arr1:
        print("1")
    else:
        print("0")

이런 식으로 쉽게 되나??했는데 역시나 예상대로 안됐다.

찾아보니 파이썬에서 in 연산자를 리스트에 이용할 경우 순차 탐색을 하기 때문에 시간복잡도는 O(N)이라고 한다. 이 문제는 최악의 경우 연산 횟수가 10^5 * 10^5 = 10^10이므로 이 문제에 주어진 제한시간인 1초 내에 문제를 해결할 수 없다.

따라서 시간복잡도가 O(logN)인 이분탐색을 이용했다.

이분탐색을 이용하기 위해 A 배열은 미리 sort()를 이용하여 오름차순으로 정렬하여 주었다.