[Python] 백준 1920번 - 수 찾기

1. 문제정보

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

1920번: 수 찾기

 

2. 해결전략

탐색에 관련된 문제로 자연수의 개수는 10만개이고, 범위는 정수형 범위입니다. 단순 이중 포문의 경우 최대 100억회(10만 x 10만)를 수행하기 때문에 시간 초과가 발생할 것입니다. 다른 방법으로는 계수 정렬 후 인덱스로 접근하려고 했지만 범위가 정수형 범위이기 때문에 역시 무리라고 판단했습니다.

 

 위와 같은 이유로 이중 탐색으로 구현했으며 이중 탐색의 경우 정렬된 리스트가 전제 조건이기 때문에 주의해야 합니다.

 

3. 코드

import sys
n = int(input())
n_array = list(map(int, input().split()))
n_array.sort()

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

def binary_search(arr, target, start, end):
    if start > end:
        return None

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


for i in m_array:
    if binary_search(n_array, i, 0, len(n_array)-1) == None:
        print(0)
    else:
        print(1)