백준 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=" ")