[백준] 10816번: 숫자 카드 2

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

initial

v easy q with hashmap. But it can be solved with binary search. how??

import sys
from collections import defaultdict

input = sys.stdin.readline

n=int(input())
lst=list(map(int,input().split()))
m=int(input())
hola=list(map(int,input().split()))
ans=defaultdict(int)
real_ans=[]
for i in lst:
    ans[i]+=1
for i in hola:
    real_ans.append(ans[i])
print(*real_ans)

sol

With binary search, we search for the left and right index where our target number is. Then, subtracting right with minus gives us the frequency of that target number in our list. The key is the bisect_left function, which has time complexity of log N.

import sys
from bisect import bisect_left, bisect_right

input = sys.stdin.readline

n = int(input())  # Read the number of cards Sanggeun has
lst = list(map(int, input().split()))  # List of cards Sanggeun has
m = int(input())  # Number of queries
hola = list(map(int, input().split()))  # The target numbers to check

# Sort the list of cards for binary search
lst.sort()

# Function to find the count of a target in the sorted list
def count_occurrences(lst, target):
    left = bisect_left(lst, target)  # Find first occurrence
    right = bisect_right(lst, target)  # Find one past the last occurrence
    return right - left  # The count is the difference between the two indices

# For each query, find the count of that target in lst
real_ans = [count_occurrences(lst, target) for target in hola]

# Print the results as space-separated integers
print(*real_ans)

complexity

1. Sorting the List:

   • Before performing binary search, we need to sort the list of coordinates.
   • Sorting a list of size N has a time complexity of O(N log N).

2. Handling Each Query:

   • For each query, we use binary search to find the first and last occurrences of a number in the sorted list:
     • bisect_left(lst, target) performs a binary search to find the index of the first occurrence of the target. It runs in O(log N) time.
     • bisect_right(lst, target) performs a binary search to find the index of one past the last occurrence of the target. It also runs in O(log N) time.

3. Final Complexity:

   • Sorting the list of size N takes O(N log N).
   • For each query, performing two binary search operations takes O(log N).
   • If there are M queries, the total time complexity for handling all queries is O(M log N).

Therefore, the overall time complexity is:

• O(N log N) for sorting the list of coordinates.
• O(M log N) for processing each query.

Thus, the final total time complexity is:

• O(N log N + M log N).

1. Space for the Sorted List:

   • The list lst stores N elements. Sorting it in place requires O(N) additional space.

2. Space for Storing Results:

   • We store the results of each query in a list of size M, so the space for the result is O(M).

3. Binary Search Operations:

   • Each binary search (bisect_left and bisect_right) operates in O(1) extra space, as they work directly on the list.

Final Space Complexity:

• O(N) for storing the sorted list of coordinates.
• O(M) for storing the results of each query.

Thus, the overall space complexity is:

• O(N + M).

Summary:

• Time Complexity: O(N log N + M log N)
• Space Complexity: O(N + M)

This approach is efficient and scales well for large input sizes.