[LeetCode] 2342. Max Sum of a Pair With Equal Sum of Digits (Python)

 

 

난이도: Medium

문제 설명

---

 

You are given a 0-indexed array nums consisting of positive integers. You can choose two indices i and j, such that i != j, and the sum of digits of the number nums[i] is equal to that of nums[j].

 

Return the maximum value of nums[i] + nums[j] that you can obtain over all possible indices i and j that satisfy the conditions.

 

문제 예제

---

Example 1:

Input: nums = [18,43,36,13,7]
Output: 54
Explanation: The pairs (i, j) that satisfy the conditions are:
- (0, 2), both numbers have a sum of digits equal to 9, and their sum is 18 + 36 = 54.
- (1, 4), both numbers have a sum of digits equal to 7, and their sum is 43 + 7 = 50.
So the maximum sum that we can obtain is 54.

Example 2:

Input: nums = [10,12,19,14]
Output: -1
Explanation: There are no two numbers that satisfy the conditions, so we return -1.

 

제한 사항

---

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109

 

✏️ Solution(솔루션)

---

class Solution:
    def maximumSum(self, nums: List[int]) -> int:
        count = defaultdict(list)
        answer = -1

        for num in nums:
            sum_digit = sum(list(map(int, str(num))))
            heapq.heappush(count[sum_digit], -num)
        
        for k, v in count.items():
            if len(count[k]) > 1:
                i = heapq.heappop(count[k])
                j = heapq.heappop(count[k])

                answer = max(answer, -i-j)
        
        return answer

 

 

먼저 nums의 모든 요소에 대해 sum of digits값을 구했다.

 

문제에서 말하는 sum of digit을 간단하게 표현하면 다음과 같다. --> (num = 18, sum of digits = 1 + 8 = 9)

 

그리고 num의 sum of digit을 key로 하는 딕셔너리에 num을 추가해주었다.

   --> num = 18, count[9] = [18] 

   --> num = 36, count[9] = [18, 36]

   . . .

 

모든 nums의 요소에 대해 진행했으면 count 딕셔너리에서 각각의 key에 대해 value의 길이가 2이상이면 pair를 만들 수 있다고 판단할 수 있다. 

 

문제에서는 이러한 num pair의 합이 최대가 되는 것을 반환하라고 했기 때문에 heapq를 사용했다.

 

왜냐하면 2개 보다 많은 num들이 있을 때, 거기서 최대가 되는 pair 합은 제일 큰 num과 그 다음으로 큰 num을 더하면 되기 때문이다.

 

따라서 sum of digit을 key로하는 딕셔너리에도 heapq를 통해 num을 추가해줬고, 마지막에 딕셔너리의 모든 key에 대해 탐색하면서 value의 길이가 2 이상이면 heappop을 두번 시행했고 이렇게 나온 값들을 더해주었다.

 

이제 이 더해준 값을 answer와 계속 비교하여 큰 값으로 업데이트 해주었다.

 

마지막에는 이러한 answer를 반환하고 정답을 맞출 수 있었다.

 

---

 

나는 각 num에 대해 sum of digits을 다음과 같이 구하긴 했는데 시간적으로 좋은 것 같진 않다.

for num in nums:
    sum_digit = sum(list(map(int, str(num))))

 

 

다음과 같이 sum of digits을 구하면 시간적으로 더 효율적으로 동작한다.

def get_sum_digit(num):
	sum_digit = 0

    while num != 0:
        sum_digit += num % 10
        num //= 10
            
    return sum_digit

for num in nums:
    sum_digit = get_sum_digit(num)

---

 

문제: 2342. Max Sum of a Pair With Equal Sum of Digits 

 

깃허브: github

algorithmPractice/LeetCode/2473-max-sum-of-a-pair-with-equal-sum-of-digits at main · laewonJeong/algorithmPractice