10816 숫자 카드 2

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

10816번: 숫자 카드 2

 

아이디어

1. N, M 숫자가 매우 큼 => 단순히 for문을 돌면 시간 초과

2. 시간 복잡도를 줄여야 하고 O(n)에서 O(logn)으로 줄이기 위해 이분 탐색 알고리즘 사용

N = int(input())
cards = list(map(int, input().split(" ")))
M = int(input())
targets = list(map(int, input().split(" ")))

sorted_cards = sorted(cards)

card_count = {}

for card in cards:
    if card not in card_count.keys():
        card_count[card] = 1
    else:
        card_count[card] += 1


def search(aim, start, end):
    if start > end:
        return 0

    mid = (start + end) // 2

    if aim == sorted_cards[mid]:
        return card_count[sorted_cards[mid]]
    elif aim > sorted_cards[mid]:
        return search(aim, mid + 1, end)
    else:
        return search(aim, start, mid - 1)


res = []
for target in targets:
    res.append(str(search(target, 0, len(cards) - 1)))

print(" ".join(res).strip())