[백준][Python][10815][이분탐색] 숫자 카드

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

10815번: 숫자 카드

이분탐색 문제다.

 

list.count() 는 O(N) 이므로, count 를 사용할 경우 O(N^2) 가 되어 시간초과가 된다.

https://wiki.python.org/moin/TimeComplexity

TimeComplexity - Python Wiki

따라서, 이분탐색을 적용해야 한다.

이분탐색을 적용하면 끝난다.

 

import sys


def binary_search(target, data):
    start = 0
    end = len(data) - 1

    while start <= end:
        mid = (start + end) // 2
        if data[mid] == target:
            return mid 
        elif data[mid] < target:
            start = mid + 1
        else:
            end = mid -1

    return None

n = int(sys.stdin.readline())
a = sys.stdin.readline().rstrip().split()
m = int(sys.stdin.readline())
b = sys.stdin.readline().rstrip().split()

a = sorted([int(i) for i in a])
b = [int(i) for i in b]



ans = []
for i in range(len(b)):
    if binary_search(b[i],a) == None:
        ans.append(0)
    else:
        ans.append(1)


for i in ans[:len(ans)-1]:
    sys.stdout.write(str(i) + ' ')

sys.stdout.write(str(ans[-1]))