숫자 카드 2 - 10816번

이분탐색을 연습하고 싶어서 고른 문제이다.

하지만 이상하게도 이분탐색을 사용하여 풀면 시간초과가 뜬다.

따라서 key로 데이터를 접근하고 관리하는 map 을 사용하여 풀었다.

이진탐색트리는 O(log n)의 속도를 가지고, 해시 맵은 O(1)의 속도를 가진다.

 

# 해시 맵을 사용하여 푼 코드, 이진탐색에 비해 더 간단한 느낌이 든다...
n = int(input())
n_arr = list(map(int, input().split()))
m = int(input())
m_arr = list(map(int, input().split()))

result = []
dict = {}


for i in n_arr:
    if i in dict:
        dict[i] +=1
    else:
        dict[i] = 1

for i in m_arr:
    if i in dict:
        print(dict[i],end=' ')
    else:
        print(0, end = ' ')

# 이진탐색을 이용하여 푼 코드, 시간초과가 뜨지만 답은 잘 나온다. 파이썬만의 문제인가???
n = int(input())
n_arr = list(map(int, input().split()))
m = int(input())
m_arr = list(map(int, input().split()))

n_set = list(set(n_arr))

# 이분탐색 함수
def bin_search(target, arr):
    arr.sort()
    start = 0
    end = len(arr)-1

    while start <= end:
        mid = (start+end)//2

        if arr[mid] == target:
            return mid
        elif arr[mid]>target:
            end = mid-1
        else:
            start = mid+1
    return None

for i in m_arr:
  res = bin_search(i, n_set)
  if res != None:
    print(n_arr.count(i),end=' ')
  else:
    print(0,end=' ')