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

Problem

 

Solution

Hash

 

보통 배열의 길이가 10^5 이하이면 2중 for문은 안쓰는게 상책. time out이 발생할 확률이 99%이기 때문

어떤 index인지는 i != j 조건만 만족하면 되므로 nums를 먼저 오름차순으로 정렬 후 시작한다.

동일한 sumDigit 을 가지는 인덱스를 hashMap으로 저장한 다음에 가장 마지막과 마지막에서 2번째 인덱스의 nums[i] + nums[j] 를 구하여 max 값을 갱신한다.

가장 마지막과 2번째로 마지막 인덱스를 구하는 이유는 처음에 오름차순 정렬을 했으므로 가장 뒤쪽의 인덱스일수록 nums[i]가 큰 정수값이기 때문이다.

 

Code

class Solution:
    def maximumSum(self, nums: List[int]) -> int:
        answer = -1
        map = defaultdict(list) #key= sum of digits, value= indicies
   
        nums.sort()

        def getSumOfDigit(num: int):
            res = 0
            while(num > 0):
                res += num%10
                num = num//10
            return res
        
        for i in range(len(nums)):
            sumDigit = getSumOfDigit(nums[i])
            map[sumDigit].append(i)
        
        for k,v in map.items():
            if len(v) >= 2:
                idx1 = v[-1]
                idx2 = v[-2]
                answer = max(nums[idx1] + nums[idx2], answer)
        return answer

 

Complexity

Time Complexity

nums.sort() -> O(nlogn)

for문 -> O(N)

 

Space Complexity

map dictionary -> O(N)