[LeetCode] 1262. Greatest Sum Divisible by Three (Swift, Python)

Greatest Sum Divisible by Three - LeetCode

 

풀이

 sums라는 원소 3개를 가진 배열을 하나 만들어서 사용하였다. 각각의 원소는 3으로 나눴을 때 나오는 나머지의 최대 합계를 나타낸다. 즉, sums[0]에는 3으로 나누어 떨어지는 숫자의 합 중 최댓값이 들어있다.

 

 입력으로 주어진 nums 배열을 순차적으로 탐색해가며 더해주는데, 이때 각각의 sums 원소에 현재 숫자를 더해준다. 그러면 총 3개의 값이 나오는데 각각을 3으로 나누었을 때 나머지에 맞춰 sums 배열에 최대값으로 갱신해준다. 이렇게 nums의 끝까지 탐색하고 나면 sums[0]에 3으로 나누어 떨어지는 숫자들의 합에 대한 최댓값이 들어있게 된다. 

 

코드

[Swift]

class Solution {
    func maxSumDivThree(_ nums: [Int]) -> Int {
        // sums[mod] : 3으로 나누었을 때 mod가 나오는 숫자들의 합에 대한 최댓값
        var sums: [Int] = [0, 0, 0]
        
        for num in nums {
            var modSums: [Int] = []
            
            // num을 각각의 sums에 더해준다.
            for i in 0..<3 {
                modSums.append(sums[i] + num)
            }
            
            // 이렇게 구한 총 3개의 합에 대해서 3으로 나누어보고
            // 나머지에 맞춰 sums 배열을 최댓값으로 갱신한다.
            for i in 0..<3 {
                let mod: Int = modSums[i] % 3
                sums[mod] = max(sums[mod], modSums[i])
            }
        }
        
        // 최종적으로 sums[0]에는 3으로 나누어 떨어지는
        // 숫자들의 합에 대한 최댓값이 들어있다.
        return sums[0]
    }
}

 

[Python]

class Solution(object):
    def maxSumDivThree(self, nums):
        # sums[mod] : 3으로 나누었을 때 mod가 나오는 숫자들의 합에 대한 최댓값
        sums = [0, 0, 0] 

        for num in nums:
            modSums = []

            # num을 각각의 sums에 더해준다.
            for i in range(3):
                modSums.append(sums[i] + num)
            
            # 이렇게 구한 총 3개의 합에 대해서 3으로 나누어보고
            # 나머지에 맞춰 sums 배열을 최댓값으로 갱신한다. 
            for i in range(3):
                mod = modSums[i] % 3
                sums[mod] = max(sums[mod], modSums[i])
        
        # 최종적으로 sums[0]에는 3으로 나누어 떨어지는 
        # 숫자들의 합에 대한 최댓값이 들어있다. 
        return sums[0]