[baekjoon]python #1920 수 찾기

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

1920번: 수 찾기

1. 쉽게 가려고 했지만...호락호락하지 않은 백준...

시간초과를 당했다.

import sys
input = sys.stdin.readline

n = int(input())
A = list(map(int,input().split()))
m = int(input())
B = list(map(int,input().split()))

for i in range(m):
    if B[i] in A:
        print(1)
    else:
        print(0)

2. 결국 이진탐색을 이용하여 문제를 다시 풀었다!

import sys
input = sys.stdin.readline

n = int(input())
A = list(map(int,input().split()))
A.sort() #이진탐색을 위한sort
m = int(input())
B = list(map(int,input().split()))


for i in range(m):
    target = B[i]
    flag = 0
    left = 0
    right = n-1
    while left<=right:
        mid = (left+right)//2
        if A[mid] == target:
            flag=1 # A안에 target이 있으면 1 
            break
        elif A[mid]> target:
            right = mid-1
        else:
            left = mid+1
    print(flag)