[백준][이분탐색] 10816. 숫자 카드2

10816. 숫자 카드2

• 첫 풀이 - fail
  • 일반 이분탐색 구조로 풀었으나
  • 이 코드는 중복되지 않는 값들로만 이루어졌을때만 가능
    • 그 이유: 중복 값 여러개 있을때 [10 10 10 10] 
    • 두번째 10 위치가  mid로 먼저 인식됐을때 앞에 값을 건너뛰어버리기 때문

n=int(input())
nums=list(map(int,input().split()))
m=int(input())
lst=list(map(int,input().split()))

nums.sort()
result=[]
for val in lst:
    cnt=0
    l,r=0,n-1
    while l<=r:
        mid=(l+r)//2

        if nums[mid]<=val:
            if nums[mid]==val:
                cnt+=1
            l=mid+1
        else:
            r=mid-1
    result.append(cnt)

print(*result)

 

 

• 두번째 풀이
  • 중복된 값이 존재하는 만큼
  • bisect으로 val, val+1 값 위치 찾아서 val의 갯수 세기

from bisect import bisect_left

n=int(input())
nums=list(map(int,input().split()))
m=int(input())
lst=list(map(int,input().split()))

nums.sort()
result=[]
for val in lst:
    cnt=0

    idx1=bisect_left(nums,val)
    idx2=bisect_left(nums,val+1)
    result.append(idx2-idx1)

print(*result)