백준 1920 수 찾기 (파이썬)

15 Apr 2021 in Dev on BOJ

1920 수 찾기 바로가기

접근방식

문제 설명에도 써있듯 이분탐색을 이용하여 수를 찾는 방법이다.
리스트에서 이 숫자가 있는가! 이렇게 간단하게 풀면 시간 초과가 뜬다.

파이썬 코드

import sys

n = int(sys.stdin.readline())
A = list(map(int,sys.stdin.readline().split()))
A.sort()
m = int(sys.stdin.readline())
m_list = list(map(int,sys.stdin.readline().split()))


def binary(A, num, low, high):
    if low > high:
        return False
    mid = (low + high) // 2
    if A[mid] > num:
        return binary(A, num, low, mid-1)
    elif A[mid] < num:
        return binary(A, num, mid+1, high)
    else:
        return True


for num in m_list:
    if binary(A,num,0,n-1):
        print(1)
    else:
        print(0)

참고

https://claude-u.tistory.com/247