백준 python 기록
백준 10816 숫자 카드 2
작지
2021. 10. 17. 03:58
백준 링크:https://www.acmicpc.net/problem/10816
10816번: 숫자 카드 2
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,
www.acmicpc.net

이분 탐색 문제.
다만 카운트를 어떻게 해야 하는지 좀 고민했다가 그냥 이분탐색 알고리즘 의 start , end부분까지 검색하기로함
import sys
input = sys.stdin.readline
def binary_search(i,s_n,start,end):
if start > end:
return 0
mid = (start + end) // 2
if i == s_n[mid]:
return s_n[start:end+1].count(i)
elif i < s_n[mid]:
return binary_search(i,s_n,start,mid-1)
else:
return binary_search(i,s_n,mid+1,end)
n = int(input())
s_n=sorted(list(map(int,input().split())))
m = int(input())
s_m=list(map(int,input().split()))
dic={}
for i in s_n:
start = 0
end = n - 1
if i not in dic:
dic[i] = binary_search(i,s_n,start,end)
for i in s_m:
if i not in dic:
print(0,end=" ")
else:
print(dic[i],end=" ")