[파이썬] 백준 알고리즘 No.10815 숫자 카드

https://acmicpc.net/problem/10815 

10815번: 숫자 카드

n = int(input())
a = list(map(int, input().split()))

m = int(input())
b = list(map(int, input().split()))

check = [0] * 20000001

for i in a:
    if i < 0:
        check[-i + 10000000] += 1
    else:
        check[i] += 1

for i in b:
    if i < 0:
        check[-i + 10000000] += 1
    else:
        check[i] += 1

for i in b:
    if i < 0:
        if check[-i + 10000000] == 2:
            print('1', end=' ')
            continue
    if check[i] == 2:
        print('1', end=" ")
    else:
        print("0", end=' ')
print()

단순 풀이 - 시간초과

 

 

 

n = int(input())
a = list(map(int, input().split()))

m = int(input())
b = list(map(int, input().split()))

a.sort()


def solution(array, target, s, e):
    while s <= e:
        m = (s + e) // 2

        if array[m] == target:
            return m
        elif array[m] > target:
            e = m - 1
        else:
            s = m + 1
    return


for i in range(m):
    if solution(a, b[i], 0, n - 1) is not None:
        print(1, end=' ')
    else:
        print(0, end=' ')

최대 2천만의 범위에서 50만개를 검색 > 이분탐색으로 가짓 수 줄이기.