[LeetCode] 2698. Find the Punishment Number of an Integer (Python)

Problem

 

Solution

recursive

주어진 n 에 대해서 1 <= i <= n 까지의 수 중 i*i 한 값의 각 자리 수 합 == i 가 되는 수들의 i*i 합을 구하는 문제.

힌트를 보니 재귀로 해당 조건을 만족하는지 체크하는 내용이었다.

 

sqared (제곱) 값을 구한 후 string 으로 변환한 뒤,  1 부터 i 까지 재귀함수를 돌며 조건을 만족하는지 체크한다. (check method)

step 1) idx = 0 자리수부터 체크하되 idx == len(sqared) 길이가 동일해지면 지금까지의 합계와 target 값이 동일한지 체크 후 반환.

step 2) 0 부터 len(sqared) 까지 각 자리수의 인덱스를 돌면서 합계를 구한다. 재귀함수를 통해서 1의 자리부터, 10의 자리부터, 100의 자리부터 계산해가며 target 값이 나올때까지 반복한다.

 

Code

class Solution:
    def punishmentNumber(self, n: int) -> int:
        def check(sq, target, idx=0, cur_sum=0):
            if idx == len(sq):
                return cur_sum == target
            num = 0
            for i in range(idx, len(sq)):
                num = num * 10 + int(sq[i])
                if cur_sum + num > target:
                    break
                if check(sq, target, i+1, cur_sum + num):
                    return True
            return False
                

        answer = 0
        for i in range(1, n+1):
            sqared = i * i
            if check(str(sqared), i):
                answer += sqared

        return answer

 

<다른 사람 풀이>

class Solution:
    def canPartition(self, num, target):
        # Invalid partition found
        if target < 0 or num < target:
            return False

        # Valid partition found
        if num == target:
            return True

        # Recursively check all partitions for a valid partition
        return (
            self.canPartition(num // 10, target - num % 10)
            or self.canPartition(num // 100, target - num % 100)
            or self.canPartition(num // 1000, target - num % 1000)
        )

    def punishmentNumber(self, n):
        p_num = 0

        # Iterate through numbers in range [1, n]
        for curr_num in range(1, n + 1):
            sq_num = curr_num * curr_num

            # Check if valid partition can be found and add squared number if so
            if self.canPartition(sq_num, curr_num):
                p_num += sq_num

        return p_num

Complexity

Time Complexity

 

 

 

Space Complexity