[Python] 백준 #10816 - 숫자 카드 2

문제

---

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

10816번: 숫자 카드 2

 

 

 

풀이

---

import sys
input = sys.stdin.readline

n = int(input())
arr1 = list(map(int, input().split()))
m = int(input())
arr2 = list(map(int, input().split()))

arr1.sort()

def upper_bound(x): # 타겟보다 큰 값이 나오는 처음 위치
    start,end=0,len(arr1)
    while start<end:
        mid = (start + end) //2
        if arr1[mid] <= x:
            start = mid + 1
        else:
            end = mid
    return end

def lower_bound(x): # 타겟과 같은 값이 나오는 처음 위치, 만약 같은 값이 없는 경우에는 타겟보다 큰 값이 나오는 처음 위치
    start,end=0,len(arr1)
    while start<end:
        mid = (start + end) //2
        if arr1[mid] < x:
            start = mid + 1
        else:
            end = mid
    return end

sol=[]
for i in arr2:
    sol.append(upper_bound(i)-lower_bound(i))
print(*sol)

 

이분탐색을 사용하고 같은 값이 나오면 while문으로 같은 값의 개수를 구해주었더니 자꾸 시간초과가 나왔다..!

구글링을 하니 upper_bound와 lower_bound를 사용해야한다고 나왔다.

 

• upper_bound : 타겟보다 큰 값이 나오는 처음 위치
• lower_bound : 타겟과 같은 값이 나오는 처음 위치, 만약 같은 값이 없는 경우에는 타겟보다 큰 값이 나오는 처음 위치

 

[1,2,3,3,3,4,5,6]

lower_bound(3) : 2

upper_bound(3) : 5

 

 

upper_bound - lower_bound를 하면 중복된 개수를 알 수 있다.