[파이썬/Python/백준알고리즘] 1920. 수찾기

첫 시도

import sys

N = int(input())
A = list(map(int,sys.stdin.readline().split()))
M = int(input())
tmp = list(map(int,sys.stdin.readline().split()))
result=[0]*M

for i in range(M):
    if tmp[i] in A:
        result[i]=1
for i in result:
    print(i)

다음과 같이 파이썬 in을 이용하여 풀이했다.

그런데 Python3으로 하면 시간초과가 나고 PyPy3으로 하면 맞다고 나온다.

그래서 인터넷에 검색해보았더니 이진탐색을 쓰는 풀이라고한다.

이진탐색 이용

import sys
def binary_sort(x,a):
    start=0
    end=len(a)-1
    while (start <= end):
        mid = (start+end)//2
        if x == a[mid]:
            return 1
        elif x > a[mid]:
            start = mid+1
        else:
            end = mid-1
    return 0

N = int(input())
A = list(map(int,sys.stdin.readline().split()))
A.sort()

M = int(input())
X = list(map(int,sys.stdin.readline().split()))
for x in range(M):
    print(binary_sort(X[x],A))