Leetcode 1262. Greatest Sum Divisible by Three

문제

Given an integer array nums, return the maximum possible sum of elements of the array such that it is divisible by three.

• 정수 배열이 주어질때, 숫자를 골라 3으로 나눠지면서 합이 최대가 되는것을 찾고
• 그 합을 리턴하시오

예시

Input: nums = [3,6,5,1,8]
Output: 18

• 3 + 6 + 1 + 8 = 18 이다.

제한

• $1 <= nums.length <= 4 * 10^4$
• $1 <= nums[i] <= 10^4$

풀이

1. 전체 합을 구한다.
2. 나머지별 리스트를 구한다.
3. 나머지별 리스트에서 1과 2가 남는 부분만 정렬한다.
4. 전체 합의 나머지가 1일때

• 나머지가 1인것중 작은것 1개를 빼거나 2인것중 작은것 2개를 뺀다.

5. 전체 합의 나머지가 2일때

• 나머지가 2인것중 작은것 1개를 빼거나 1인것중 작은것 2개를 뺀다.
• 리턴

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        cntr = defaultdict(list)

        for num in nums:
            cntr[num % 3].append(num)

        ans = sum(nums)

        cntr[1].sort()
        cntr[2].sort()

        O, T = len(cntr[1]), len(cntr[2])
        o = cntr[1]
        t = cntr[2]

        if ans % 3 == 0:
            return ans
        elif ans % 3 == 1:
            a, b = 0, 0
            if O >= 1:
                a = ans - o[0]
            if T >= 2:
                b = ans - t[0] - t[1]
            return max(a, b)
        else:
            a, b = 0, 0
            if O >= 2:
                a = ans - o[0] - o[1]
            if T >= 1:
                b = ans - t[0]
            return max(a, b)