825. Friends Of Appropriate Ages (Array, Two Pointers, Binary Search, Sorting)

링크 - https://leetcode.com/problems/friends-of-appropriate-ages/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

1) Counter

우리는 age의 범위가 1부터 120까지임을 알 수 있으므로, age에 대한 counter를 구한 뒤, age끼리만 계산하면 모든 ages를 계산하지 않아도 된다.

class Solution(object):
    def numFriendRequests(self, ages):
        count = [0] * 121
        for age in ages:
            count[age] += 1

        ans = 0
        for ageA, countA in enumerate(count):
            for ageB, countB in enumerate(count):
                if ageA * 0.5 + 7 >= ageB: continue
                if ageA < ageB: continue
                if ageA < 100 < ageB: continue
                ans += countA * countB
                if ageA == ageB: ans -= countA

        return ans

Time Complexity: O(A^2 + N) 여기서 A는 ages의 개수이고, N은 사람의 개수이다.

Space Complexity: O(A)

2) Binary Search

 

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        ans = 0
        n = len(ages)
        ages.sort()

        def bs(val, left = 0, right = len(ages)):
            while left < right:
                mid = (left + right) // 2
                if val < ages[mid]:
                    right = mid
                else:
                    left = mid + 1
            return left

        for i in range(n):
            a = ages[i]
            idx1 = bs(a)
            idx2 = bs(0.5*a + 7)
            # idx1 = bisect.bisect(ages, a)
            # idx2 = bisect.bisect(ages, 0.5 * a + 7)
            ans += max(0, idx1 - idx2 - 1)

        return ans

Time Complexity: O(nlogn)

Space Complexity: O(1)