[백준] 10816번 숫자 카드 2 ★

💡문제접근

• "숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다." 부분은 이분 탐색 알고리즘을 이용하라는 의미였다. 선형 탐색으로 이 과정을 진행한다면 엄청난 시간이 소모되기 때문에 이분 탐색을 이용해야하는 문제였다.
• WA보다는 시간초과가 상대적으로 더 빈번하게 나온 문제였다.

💡코드(메모리 : 115188KB, 시간 : 2416ms)

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 data[start:end+1].count(target)
        elif data[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return 0

N = int(input())
A_li = list(map(int, sys.stdin.readline().strip().split()))
M = int(input())
B_li = list(map(int, sys.stdin.readline().strip().split()))

A_li.sort()
dict = {}
for i in B_li:
    if i not in dict:
        dict[i] = binary_search(i, A_li)

for i in B_li:
    print(dict[i], end = " ")

💡소요시간 : 43m