백준 10816번: 숫자 카드 2

10816번: 숫자 카드 2 (acmicpc.net)

10816번: 숫자 카드 2

 

Lower bound는 찾고자 하는 숫자이상의 값이 처음으로 나오는 인덱스 값을 반환하고
Upper 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

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

for i in M:  
d.append(upper_bound(0, n, i) - lower_bound(0, n, i))  
print(*d)  

코드 참고

Lower bound, Upper bound (python) (velog.io)

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