[LeetCode] 923 | 3Sum With Multiplicity | Python

---

문제 링크: https://leetcode.com/problems/3sum-with-multiplicity/

---

문제

Given an integer array arr, and an integer target, return the number of tuples i, j, k such that i < j < k and arr[i] + arr[j] + arr[k] == target.

As the answer can be very large, return it modulo 109 + 7.

---

조건

• 3 <= arr.length <= 3000
• 0 <= arr[i] <= 100
• 0 <= target <= 300

---

내 풀이

먼저 수가 최대 100까지이므로 이들의 빈도를 리스트(occur)에 저장한다.

 

target은 세 수의 합으로 이루어지기 때문에 세 수중 제일 큰 수(c)는 target/3이거나, 문제의 조건 때문에 100 중 더 작은 수가 된다.

이와 같은 원리로 두번째로 큰 수(b)는 target-c의 절반이 되고, a는 target-b-c가 된다.

이렇게 a, b, c가 정해지면 occur 리스트를 이용해 그 수를 확인한다.

---

코드

class Solution:
    def threeSumMulti(self, arr: List[int], target: int) -> int:
        self.occurs = [0 for _ in range(101)]
        for n in arr:
            self.occurs[n] += 1
        sumi = 0
        
        third = ceil(target/3) - 1
        for c in range(min(target, 100), third, -1):
            remain = target - c
            half = ceil(remain/2) - 1
            
            for b in range(min(remain, c), half, -1):
                a = remain - b
                sumi += self.get_sum([a, b, c])
                sumi = sumi % (10**9+7)
        
                        
        return sumi
    
    def get_sum(self, A):
        a, b, c = A
        
        if a == b == c:
            result = self.occurs[a] * (self.occurs[b]-1) * (self.occurs[c]-2) / 6
        elif a == b and b != c:
            result = self.occurs[a] * (self.occurs[b]-1) * self.occurs[c] / 2
        elif a != b and b == c:
            result = self.occurs[a] * self.occurs[b] * (self.occurs[c]-1) / 2
        else:
            result = self.occurs[a] * self.occurs[b] * self.occurs[c]
            
        result = result % (10**9+7)
        return int(result)