[Python] BOJ 10816 - 숫자 카드 2 (lower bound, upper bound)

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

10816번: 숫자 카드 2

주어진 배열에 대해 입력받은 숫자의 갯수를 세야 하는 문제이다. 
단순한 이분 탐색으로는 그 숫자의 위치는 찾을 수 있을지 몰라도 숫자의 갯수는 찾지 못한다.
검색을 하던도중 lower bound와 upper bound 개념을 발견했다.

 

* Lower bound는 찾고자 하는 숫자 이상의 값이 처음으로 나오는 인덱스 값을 반환하고
  Upper bound는 찾고자 하는 숫자 초과의 값이 처음으로 나오는 인덱스 값을 반환한다.

 

따라서 배열에서 찾고자하는 수의 upper_bound에서 lower_bound를 빼주면 찾고자하는 수의 갯수가 나오게 된다.

* 이분탐색에서 배열은 항상 정렬된 상태여야 한다.

n,L,k,M = int(input()),list(map(int, input().split())),int(input()),list(map(int, input().split()))
d = []
L.sort()
def upper_bound(s, e, d):
    while(e - s > 0):
        m = (s+e)//2
        if(L[m] <= d):
            s = m+1
        else:
            e = m
    return e+1
    
def lower_bound(s, e, d):
    while(e - s > 0):
        m = (s+e)//2
        if(L[m] < d):
            s = m+1
        else:
            e = m
    return e+1
    
for i in M:
    d.append(upper_bound(0, n, i) - lower_bound(0, n, i))
print(*d)