[코테연습] 2698. Find the Punishment Number of an Integer

https://leetcode.com/problems/find-the-punishment-number-of-an-integer/description/?envType=daily-question&envId=2025-02-15

 

문제 타입

• 완전 탐색 (Brute Force)
• 백트래킹 (Backtracking)
• 재귀 (Recursion)
• 문자열 조작 (String Manipulation)

---

문제 분석

• 주어진 정수 n 이하의 자연수 x에 대해 특정 조건을 만족하는 수들의 제곱 합을 구하는 문제
• Punishment Number 조건
  • x의 제곱을 여러 개의 연속된 부분 문자열로 나눌 수 있어야 함
  • 나눈 부분 문자열을 정수로 변환한 후 합이 x와 같아야 함
• 이를 만족하는 모든 x의 제곱을 더한 값을 반환해야 함

---

문제 풀이

1. 모든 숫자 1부터 n까지 탐색
   • x의 제곱을 문자열로 변환하여 탐색
   • 백트래킹을 사용하여 모든 가능한 나누는 방법을 시도
2. 백트래킹을 활용한 검증
   • x의 제곱을 부분 문자열로 나누며 합이 x가 되는지 확인
   • 현재까지의 합이 x를 초과하면 중단
   • 탐색이 끝났을 때 합이 정확히 x라면 true
3. Punishment Number 계산
   • 조건을 만족하는 숫자들의 제곱을 합산하여 최종 결과를 반환

> java

class Solution {
    public int punishmentNumber(int n) {
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            int square = i * i;
            String str = String.valueOf(square);
            if (canSplitToSum(str, 0, i, 0)) {
                sum += square; // punishment number 추가
            }
        }
        return sum;
    }

    private static boolean canSplitToSum(String str, int index, int target, int currentSum) {
        if (index == str.length()) {
            return currentSum == target; // 나눠진 숫자들의 합이 원래 숫자와 같은 경우
        }

        int num = 0;
        for (int i = index; i < str.length(); i++) {
            num = num * 10 + (str.charAt(i) - '0'); // 현재 부분 숫자 생성
            if (canSplitToSum(str, i + 1, target, currentSum + num)) {
                return true; // 백트래킹으로 성공한 경우 true 반환
            }
        }

        return false; // 가능한 조합이 없는 경우
    }
}

 

> python

 

 

class Solution:
    def punishmentNumber(self, n: int) -> int:
        _sum = 0
        for num in range(1, n+1) :
            _num = num * num
            if self.backtrack(str(_num), 0, num, 0) :
                _sum += _num

        return _sum

    def backtrack(self, _str, idx, target, current):  # \U0001f6e0 self 추가
        if idx == len(_str):
            return target == current

        num = 0
        for i in range(idx, len(_str)):  
            num = num * 10 + int(_str[i])  
            if self.backtrack(_str, i + 1, target, current + num):  
                return True

        return False