10816

a in b(set,list) 그리고 이분탐색(binary search)

a가 단순히 b에 있는지 찾을 때-> 1920번 그리고 숫자카드1 문제는 집합에서 있는지 없는지만 확인하면 됨.
하지만 10816번처럼 중복된 숫자들을 입력받고 몇개 있는지 세야할 때는 집합을 쓰면 안 됨. 집합은 중복을 없애기 때문에.
이처럼 불가피하게 리스트를 써야할 경우 인덱스 절반 갈라서 찾는 이진탐색을 씀.
시간 초과된 내 코드

import sys
input=sys.stdin.readline
def binary_search_recursion(target, start, end, data):
    if start > end:
        return None

    mid = (start + end) // 2

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

    return binary_search_recursion(target, start, end, data)
a=int(input())
b=input().split()
c=int(input())
d=input().split()
d2=sorted(d)
e=[0]*c
for i in range(a):
    n=binary_search_recursion(b[i],0,c-1,d2)
    if n!=None: #근데 이분검색 쓰려면 sort돼야되는데 이러면 순서가 바뀌어서 그래서 d2, d 이용하는 거
        e[d.index(b[i])] +=1
print(e)

bisect

import bisect
bisect.bisect(배열, 찾는 거)
bisect는 찾는 게 배열 안 원소와 일치하면 해당 원소 기준 오른쪽 인덱스를 반환. 1을 찾는데 [1,2,3] 여기서 찾으면 0이 아니라 1을 반환.
bisect.left()
bisect.right()
썼지만 여전히 시간초과

import sys
import bisect
input=sys.stdin.readline
#bisect를 이진탐색대신 
a=int(input())
b=input().split()
c=int(input())
d=input().split()
d2=sorted(d)
e=[0]*c
for i in range(a):
    n=bisect.bisect(d2,b[i])-1 # 1 2 3 에서 1이 들어갈 곳 리턴-> 이땐 1을 반환함. 오른쪽에 들어간다고 봄. 그니까 -1해줘야
    if n!=None: #근데 이분검색 쓰려면 sort돼야되는데 이러면 순서가 바뀌어서
        e[d.index(d2[n])] +=1
print(e)
# b= 1 1 1 2 3
# d= 2 3 1
# d2= 1 2 3