10816 숫자 카드 2 - Python

from collections import defaultdict

n = int(input())
cards = list(map(int, input().split()))
m = int(input())
targets = list(map(int, input().split()))
card_count = defaultdict(int)

for card in cards:
    card_count[card] += 1

for target in targets:
    print(card_count[target], end=' ')

  딕셔너리로 풀었습니다. 이 문제인 경우 숫자 카드가 많이 크기에  일반적으로 많은 시간이 소요됩니다. 이런 경우 이분법으로 풀어야 하지만 파이썬의 경우 딕셔너리를 지원하기에 시간 복잡도 우위를 가집니다.

 

---

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    count = 0
    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            while arr[mid] == target:
                mid -= 1
                if mid == -1:
                    break
            mid += 1
            while arr[mid] == target:
                count += 1
                mid += 1
                if mid == len(arr):
                    break
            return count
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return count


card_num = int(input())
inputs = sorted(map(int, input().split()))

cases = int(input())
target = list(map(int, input().split()))
for i in range(cases):
    temp = binary_search(inputs, target[i])
    print(f"{temp} ")

  이 풀이는 제가 이분법으로 푼 건데 결과는 시간초과입니다. 어떻게 해야 이분법으로 시간 내에 통과가 될 지... ChatGPT한테 도움을 받았습니다.

 

---

def binary_search_first(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            if mid == 0 or arr[mid - 1] != target:
                return mid
            else:
                right = mid - 1
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1


def binary_search_last(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            if mid == len(arr) - 1 or arr[mid + 1] != target:
                return mid
            else:
                left = mid + 1
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1


n = int(input())
cards = sorted(list(map(int, input().split())))
m = int(input())
targets = list(map(int, input().split()))

for target in targets:
    first_idx = binary_search_first(cards, target)
    last_idx = binary_search_last(cards, target)

    if first_idx == -1:
        print(0, end=' ')
    else:
        print(last_idx - first_idx + 1, end=' ')

  저는 한번에 처리하려 했는데 두 번 나누는게 더 빠르네요.

 

---

• 백준: https://www.acmicpc.net/problem/10816

10816번: 숫자 카드 2