[백준]10816 숫자카드2

1.풀이

처음에 이진탐색을 해서 숫자x가 있는지 확인한 이후, 있다면 해당 위치에서 앞뒤로 이동하며 몇개있는지 세는 식으로 문제를 풀었다. 하지만 이런 방법은 숫자 x가 500,000개 있다면, 50만번을 수행해야 하므로 시간초과가 걸린다.(소스코드1)

따라서 숫자 x<=L[I]인 가장 작은 i (lower bound)와, 숫자x<L[i]인 가장작은 i (upper bound)를 이진탐색을 이용해 구한 뒤, upper bound- lower bound​를 해주어서 문제를 푼다.

​

2.소스코드

(1) 시간초과

N=int(input())
card=list(map(int,input().split()))
card.sort()
M=int(input())
L=list(map(int,input().split()))

def binarySearch(target):
    left=0
    right=N-1
    loc=-1
    while(left<=right):
        mid=(left+right)//2
        if target<card[mid]:
            right=mid-1
        elif target>card[mid]:
            left=mid+1
        else:
            loc=mid
            break


    if loc==-1:
        return 0
    else:
        cnt = -1
        for i in range(loc,N):
            if card[i]==target:
                cnt+=1
            else:
                break
        for i in range(loc,-1,-1):
            if card[i]==target:
                cnt+=1
            else:
                break
        return cnt

for i in L:
    print(binarySearch(i),end=" ")

 

(2) 통과

N=int(input())
card=list(map(int,input().split()))
card.sort()
M=int(input())
L=list(map(int,input().split()))

# target<=L[i]인 가장 작은 i를 찾음
def leftBinary(target):
    left=0
    right=N
    while(left<right):
        mid=(left+right)//2
        if target<=card[mid]:
            right=mid
        else:
            left=mid+1
    return right

# target<L[i]인 가장 작은 i를 찾음
def rightBinary(target):
    left=0
    right=N
    while(left<right):
        mid=(left+right)//2
        if target<card[mid]:
            right=mid
        else:
            left=mid+1
    return right

for i in L:
    r=rightBinary(i)
    l=leftBinary(i)
    print(r-l,end=" ")