[Dart] 202. Happy Number

1. 문제

https://leetcode.com/problems/happy-number/?envType=study-plan-v2&envId=top-interview-150

 

 

 

2. 요구사항

1) 임의의 양의 정수 n이 주어진다.

2) 숫자의 각 자리 숫자를 제곱한 값을 모두 더한다.

3) 숫자 1이 될 때까지 이 과정을 반복한다.

4) 이 과정이 1로 끝나면 이 숫자는 해피 넘버이다.

5) 해피 넘버이면 true를 반환하고, 그렇지 않으면 false를 반환한다.

 

 

 

3. 핵심 아이디어

1) 언젠가 한 자리 수로 수렴

 

아무리 큰 숫자라도 각 자릿수의 제곱을 반복적으로 더하다 보면 언젠가는 일의자리 수로 수렴하게 된다.

 

또한, 한 자리 수가 1이나 7이면 해당 숫자는 해피 넘버이다.

이 외의 숫자는 사이클을 형성하게 되어 무한 반복하게 된다.

 

숫자	경로
1	1
2	2 → 4
3	3 -> 9
4	4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4
5	5 → 25 → 29 → 85 → 89 → …
6	6 → 36 → 45 → 41 → 17 → 50 → 25 → 29 → 85 → 89 → ...
7	7 → 49 → 97 → 130 → 10 → 1
8	8 → 64 → 52 → 29 → 85 → 89 → …
9	9 → 81 → 65 → 61 → 37 → 58 → 89 → ...

 

 

 

2) 코드

class Solution {
  bool isHappy(int n) {
    
    // n이 한 자리 수가 될 때까지 반복
    while (n > 9) {
      int sum = 0;       // 자릿수 제곱합을 저장할 변수
      int temp = n;      // 자릿수 분리를 위한 임시 변수

      // 각 자리 숫자를 분리하고 제곱하여 합산
      while (temp > 0) {
        int digit = temp % 10;       // 마지막 자리 숫자
        sum += digit * digit;        // 제곱해서 누적 합산
        temp ~/= 10;                 // 다음 자리로 이동 (정수 나눗셈)
      }

      n = sum; 						// n을 새로운 제곱합으로 갱신
    }

    // 최종적으로 n이 1 또는 7이면 happy number
    return n == 1 || n == 7;
  }
}

 

시간 복잡도 : O(log n)

 - 자릿수 분리와 반복 횟수

 

공간 복잡도 : O(1)

 

 

 

3) 순환되는 숫자를 Set로 저장

 

해피 넘버가 아닌 숫자는 각 과정을 무한으로 순환한다.

순환되는 과정에서 중복되는 숫자가 있을텐데 이를 확인하기 위한 작업이 Set 변수를 선언하는 것이다.

Set는 중복을 허용하지 않기 때문에 각 과정을 거치면서 각 제곱의 합을 Set에 저장한다.

 

만약, 순환하면서 Set에 등록된 숫자가 나온다면 이는 무한 순환하기 때문에 해피 넘버가 아닐 것이다.

 

 

4) 코드

class Solution {
  // 숫자가 해피 넘버인지 판별
  bool isHappy(int n) {
    Set<int> seen = {};     // 중복을 확인하기 위한 Set (무한 루프 방지)
    
    while (n != 1 && !seen.contains(n)) {
      seen.add(n);          // 현재 숫자를 Set에 추가
      n = getSqureSum(n);   // 자릿수 제곱합으로 숫자 갱신
    }

    // 숫자가 1이면 해피 넘버이므로 true 반환
    return n == 1;
  }

  // 각 자릿수의 제곱을 모두 더한 값을 반환
  int getSqureSum(int n) {
    int sum = 0;

    while (n > 0) {
      int digit = n % 10;      // 마지막 자리 숫자 추출
      sum += digit * digit;    // 제곱해서 합산
      n ~/= 10;                // 다음 자리로 이동 (정수 나눗셈)
    }

    return sum;                // 최종 제곱합 반환
  }
}

 

시간 복잡도 : O(log n)

 - 자릿수 분리와 반복 횟수

 

공간 복잡도 : O(k)

 - Set에 저장되는 숫자 개수