[Python] BOJ 10816 - 숫자 카드 2

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

10816번: 숫자 카드 2

[2022.02.17]

- 이분탐색으로 해결하면 정답 나옴.

 

N = int(input())
numbers = list(map(int, input().split()))
M = int(input())
task = list(map(int, input().split()))

new_dict = {}
for n in numbers:
    if n not in new_dict:
        new_dict[n] = 1
    else:
        new_dict[n] += 1

numbers.sort()


def binary(m):
    l = 0
    r = len(numbers) - 1
    while 1:
        m = (l + r) // 2
        if numbers[m] == t:
            return new_dict[t]
        elif numbers[m] > t:
            r = m - 1
        else:
            l = m + 1

        if l > r:
            return 0

cnt = []
for t in task:
    cnt.append(binary(t))
print(*cnt)