[LeetCode] 202. Happy Number

202. Happy Number

LeetCode

https://leetcode.com/problems/happy-number/description/

Happy Number - LeetCode

Write an algorithm to determine if a number n is happy.
A happy number is a number defined by the following process:
Starting with any positive integer, replace the number by the sum of the squares of its digits.Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.Those numbers for which this process ends in 1 are happy.
Return true if n is a happy number, and false if not.

숫자 n이 행복한 수(happy number)인지 판별하는 알고리즘을 작성하세요.
행복한 수는 다음 과정을 통해 정의되는 숫자입니다: 양의 정수에서 시작하여, 해당 숫자를 각 자릿수의 제곱의 합으로 바꿉니다. 이 숫자가 1이 될 때까지(1이 되면 머무름), 또는 1을 포함하지 않고 무한히 반복되는 사이클에 빠질 때까지 이 과정을 반복합니다. 이 과정이 1로 끝나는 숫자들이 바로 '행복한 수'입니다.
n이 행복한 수라면 true를 반환하고, 그렇지 않다면 false를 반환하세요.

 

Example

Input: n = 19
Output: true
Explanation:
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

Input: n = 2
Output: false

---

1. 문제 요구사항 분석

숫자를 1의 자리, 10의 자리, 100의 자리 다 분리한 후, 그것의 배수들을 더해 1이 나오면 행복한 숫자, 그렇지 않고 무한반복이 되면 false가 된다.

2. 접근 전략

토끼와 거북이 알고리즘을 다른 문제에도 적용해보기 위해 고른 문제

😁 투 포인터

class Solution {
    public boolean isHappy(int n) {
        int slow = n; // 거북이
        int fast = getNext(n); // 토끼 (시작부터 1칸 앞서감)
        
        // 토끼가 결승선(1)에 도달하거나, 거북이와 만나기 전까지 반복
        while (fast != 1 && slow != fast) {
            slow = getNext(slow); // 거북이는 1번 연산 (1칸 이동)
            fast = getNext(getNext(fast)); // 토끼는 2번 연산 (2칸 이동)
        }
        
        // 토끼가 1에 도착해서 끝난 거라면 true(해피), 사이클이라 만난 거라면 false
        return fast == 1;
    }
    
    // 각 자릿수의 제곱의 합을 구하는 메서드 (다음 연산) 
    private int getNext(int n) {
        int totalSum = 0;
        while (n > 0) {
            int d = n % 10; // 일의 자리 숫자 추출
            n = n / 10; // 남은 숫자
            totalSum += d * d; // 제곱해서 더하기
        }
        return totalSum;
    }
}