[백준] [이분탐색] 10816. 숫자 카드 2

10816. 숫자 카드 2

10816번: 숫자 카드 2

 

 

• 내 풀이
  • 실버4인데 반례를 못찾아서 몇일 걸린 문제.....;;
  • check에 중복이 들어오는데 연속되지 않고 같은 수가 따로따로 들어올 수 있음
    • -> 같은 값 불러오려면 딕셔너리 인덱스로 값 찾아야함
• 반례

10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 10

#결과
3 0 0 1 2 0 0 3

import sys
input=sys.stdin.readline
n=int(input())
lst=list(map(int,input().split()))
m=int(input())
check=list(map(int,input().split()))
result=[0]*m


# -10 -10 2 3 3 6 7 10 10 10
def bin(start, end, i):
    x=check[i]
    if start>end:
        return

    mid=(start+end)//2
    if lst[mid]==x:
        result[i]=lst[start:end+1].count(x)
        return

    if x>lst[mid]:
        bin(mid+1, end, i)
    else:
        bin(start, mid-1, i)

find={}
lst.sort()
for i,c in enumerate(check):
    if c in find:
        result[i]=find[c]
        continue
    bin(0,n-1,i)
    find[c]=result[i]

for r in result:
  print(str(r), end=" ")