[백준] 파이썬 숫자 카드 2

이분탐색으로 O(logN) 시간복잡도로 풀어보자
명심해야할 사실은 이분탐색은 항상 정렬된 배열에서 탐색가능하다

모듈없이 풀기

if __name__ == "__main__":
    def lower(target):
        left = 0
        right = len(cards)
        while left < right :
            mid = (left + right) // 2
            if cards[mid] >= target:
                right = mid
            else :
                left = mid + 1
        return right

    def upper(target):
        left = 0
        right = len(cards)
        while left < right :
            mid = (left + right) // 2
            if cards[mid] > target :
                right = mid
            else :
                left = mid + 1
        return right


    N = int(input())
    cards = list(map(int,input().split()))
    M = int(input())
    numbers = list(map(int,input().split()))
    cards.sort()

    for number in numbers:
        print(upper(number)-lower(number),end=" ")

• 알고리즘이 헷갈린다. if else문에서 등호는 어디에 들어가야하는지 언제 mid + 1 해야하는지 헷갈림
• 완벽히 이해하지 않는 이상 계속 헷갈릴듯 ...

모듈 사용해서 풀기

import bisect

N = int(input())
cards = list(map(int,input().split()))
M = int(input())
numbers = list(map(int,input().split()))
cards.sort()

for number in numbers:
    print(bisect.bisect_right(cards,number)-bisect.bisect_left(cards,number),end=" ")

• 파이썬의 이지탐색 내장모듈 bisect 사용

• bisect_right는 upperBound

• bisect_left는 lowerBound 값을 반환한다

• 모듈을 사용하니 너무 쉽다. lower, upper 알고리즘을 이해하고 난 뒤에는 모듈을 적극적으로 사용해야겠다