재귀호출 :: 하나의 트리 구조로 호출하기

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

📖 각 자리 숫자의 제곱

8자리 이하의 정수 N이 주어지면 재귀함수를 이용하여 각 자리 숫자의 제곱의 합을 출력하는 프로그램을 작성해보세요.

입력 형식

첫 번째 줄에 정수 N이 주어집니다.

• 1 ≤ N ≤ 99,999,999

출력 형식

첫 번째 줄에 정수 N의 각 자리 숫자의 제곱의 합을 출력합니다.

입출력 예제

예제1

입력:

654321

출력:

91

예제 설명

첫 번째 예제에서 입력이 654321이므로 62 + 52 + 42 + 32 + 22 + 12 = 91 이다.

제한

시간 제한: 1000ms 메모리 제한: 80MB

Solve 💡

• 초기 시도 :: 맨 앞부터 각 자리의 숫자들에 접근하기 의사코드

  1. 입력값이 1이라면 1을 반환한다. :: 최종 단계 완료 조건
  2. 654321에서 6을 가져온다.
  3. 6 * 6 + getSumEachSquare(54321)을 재귀호출
  4. 1번 조건에 의해 재귀호출이 종료될 때까지 호출

  코드

  package Codetree.ReturnRecursive;
  
  import java.util.Scanner;
  
  public class SquareOfEachNum {
      public static void main(String[] args) {
          /* input */
          Scanner scanner = new Scanner(System.in);
          int inputNum = scanner.nextInt();
          /* calc */
          int sum =getSumEachSquare(inputNum);
          /* result */
          System.out.println(sum);
      }
  
      private static int getSumEachSquare(int n) {
          String numStr = Integer.toString(n);
          int first = numStr.charAt(0) - '0';
          if (first == 1)
              return 1;
          int restNum = Integer.parseInt(numStr.substring(1, numStr.length()));
          return (first * first) +getSumEachSquare(restNum);
      }
  }

  어느 부분에서 틀린 것인가

  1을 만나야만 조건이 된다.
  => 999999와 같은 입력값은 9^2이 6번 더해져야 한다.
  => 그런데 1을 만나야 종료되게끔 구현되었으므로 위 입력값은 에러를 뿜는다.

• 해설 :: 나는 앞에서부터 했지만, 해설은 한 자리가 될 때까지 수를 쪼개버림

  package Codetree.ReturnRecursive;
  
  import java.util.Scanner;
  
  public class SquareOfEachNum {
      public static int sum(int n) {
          // 한 자리 숫자라면 제곱한 값이 결과가 됩니다.
          if (n < 10)
              return n * n;
  
          // 마지막 자리 숫자의 제곱에
          // 남은 숫자들의 합을 계산한 결과를 더해 반환합니다.
          int digit = (n % 10);
          return sum(n / 10) + digit * digit;
      }
  
      public static void main(String[] args) {
          Scanner sc = new Scanner(System.in);
  
          // 변수 선언 및 입력:
          int n = sc.nextInt();
  
          System.out.println(sum(n));
      }
  }

What I’ve Learned 📝

Theory 📜

1. 재귀호출 형태를 적은 뒤, 구조를 뜯어볼 것

   1. F(1527) = F(152) + 7*7

      ⇒ F(n) = F(n/10) + (n%10)*(n%10)

Note 📓

1. 문제의 조건사항을 넘겨짚지 말 것
2. 재귀호출은 함수스택이 쌓이지만 호출 프로세스는 트리와 같다고 생각한다.
   1. 따라서 애매하다 싶으면 트리 구조로 호출 시퀀스를 그려보는 것도 좋을 거 같다.