[백준] 10815번 숫자 카드 - 파이썬

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

10815번: 숫자 카드

문제를 보고 엥? 너무 쉬운데 하고 풀었는데

import sys

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))

m = int(sys.stdin.readline())
b = list(map(int, sys.stdin.readline().split()))


for i in range(len(b)):
    if b[i] in a:
        print(1, end= " ")
    else:
        print(0, end= " ")

당영히 시간초과

이 문제를 해결하기 위해서는 탐색 방법중 이분 탐색으로 해결해야하는 문제이다.

 

import sys

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))

m = int(sys.stdin.readline())
b = list(map(int, sys.stdin.readline().split()))
a.sort()
for i in range(len(b)):
    start = 0
    end = n-1
    flag = True
    while start <= end:
        mid = (start + end)//2

        if a[mid] > b[i]:
            end = mid - 1
        elif a[mid] < b[i]:
            start = mid + 1
        else:
            print(1 ,end = " ")
            flag = False
            break
    if flag:
        print(0,end= " ")

이렇게 해결하면 된다.