문제

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

나의 코드

"""
1. 아이디어
이분탐색 문제라 해놓고 해시로 풀어야 되는건 뭐지.. 그냥 해시 이용해서 풀면 됨

2. 시간복잡도
O(1)
"""

from sys import stdin
input = stdin.readline

n = int(input())
cards = list(map(int, input().split()))
m = int(input())
nums = list(map(int, input().split()))
answer = []

dict = {} # 해시와 맵을 이용하여 문제 해결
for card in cards: # 카드의 숫자와 개수를 딕셔너리에 입력
    if card in dict:
        dict[card] += 1
    else:
        dict[card] = 1

for num in nums: # 찾고자 하는 카드의 숫자의 개수 출력
    if num in dict:
        print(dict[num], end=" ")
    else:
        print(0, end=" ")

    

느낀점

해시 문제

아마 이분탐색으로 풀려면 2개 써야하는거 같은데 나중에 풀어보자.

• 반례에 걸려서 틀린 코드

from sys import stdin
input = stdin.readline

n = int(input())
cards = list(map(int, input().split()))
m = int(input())
nums = list(map(int, input().split()))
answer = []

def bisect(num):
    left, right = 0, n-1
    cnt = 0

    while left <= right:
        mid = (left + right) // 2

        if num > cards[mid]:
            left = mid + 1
        elif num < cards[mid]:
            right = mid - 1
        else:
            cnt += 1
            if mid+1 < n and num == cards[mid+1]:
                left = mid + 1
            elif mid-1 >= 0 and num == cards[mid-1]:
                right = mid - 1
            else:
                break
    return cnt

cards.sort()
for num in nums:
    res = bisect(num)
    answer.append(res)

print(*answer)

"""
반례
5
1 1 1 1 1
2
1 2
"""