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

https://leetcode.com/problems/max-sum-of-a-pair-with-equal-sum-of-digits/description/

leetcode - Max Sum of a Pair With Equal Sum of Digits

문제 유형: 해시, 그리디

문제 난이도: 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.

 

양의정수가 들어있는 0-indexed의 배열이 주어집니다.

두 개의 인덱스를 골라서, 만약 두 수의 모든자릿수의 합이 서로 같다면, 합을 구할 수 있습니다.

그 합의 최대를 구하시오.

 

풀이

순차적으로 하나씩 수를 읽으면서, 수의 자릿수들을 모두 더한 값을 구한다.

그 값이 해시에 없으면 그냥 저장하고, 있다면 기존 값과 더해서 최대값을 갱신하고 해시 최대값도 갱신해준다.

 

최종적인 최대값을 리턴한다.

 

코드

C++

class Solution {
public:
    int d(int x) {
        int res = 0;
        while(x > 0) {
            res += x%10;
            x/=10;
        }
        return res;
    }
    int maximumSum(vector<int>& nums) {
        unordered_map<int, int> mp;
        int ans = -1;

        for(const auto &num : nums) {
            int digest = d(num);
            if(!mp[digest]) {
                mp[digest] = num;
            } else {
                ans = max(ans, mp[digest] + num);
                mp[digest] = max(mp[digest], num);
            }
        }

        return ans;
    }
};

 

Go

func d(x int) int {
    res := 0
    for x > 0 {
        res += x%10
        x /= 10
    }
    return res
}

func maximumSum(nums []int) int {
    ans := -1
    mp := make(map[int]int)
    for _, num := range nums {
        digest := d(num)
        if val, ok := mp[digest]; !ok {
            mp[digest] = num
        } else {
            ans = max(ans, num + val);
            mp[digest] = max(val, num)
        }
    }

    return ans
}