백준 10816 숫자 카드 (이분 탐색)

from sys import stdin
input = stdin.readline

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

n_count = dict()
for i in n_list:
    if i in n_count:
        n_count[i] += 1
    else:
        n_count[i] = 1
n_list = sorted(list(n_count.keys()))

m = int(input())
m_list = list(map(int, input().split()))
result = []
for i in m_list:
    s, e = 0, len(n_list) -1
    while s <= e:
        mid = (s + e)//2
        if i == n_list[mid]:
            result.append(n_count[i])
            break
        if i < n_list[mid]:
            e = mid -1
        else:
            s = mid + 1
    else:
        result.append(0)

print(*result)

처음 N개의 카드를 입력 받을 때 딕셔너리를 통해 해당 카드의 개수를 같이 저장시키고 후에 이분 탐색으로 숫자를 찾고 있다면 딕셔너리에 저장해 놓은 개수를 출력한다.

n = int(input())
n_dic = {}
for i in input().split():
    if i in n_dic:
        n_dic[i] += [True]
    else:
        n_dic[i] = [True]
m = int(input())

for i in input().split():
    if i in n_dic:
        print(len(n_dic[i]), end= " ")
    else:
        print(0, end= " ")

이전에 풀었던 방식인데 어차피 딕셔너리의 경우 key 값을 통해 저장된 값을 찾을때의 시간 복잡도는 O(1)이므로 그냥 딕셔너리로 해결했었다.

이분탐색 보다도 더 적은 소유 시간이 나왔다... 시간 복잡도를 생각하면 당연한 결과긴 하다.