91일 (202. Happy Number) two poniters

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.

 

Example 1:

Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

Example 2:

Input: n = 2
Output: false

 

Constraints:

• 1 <= n <= 2^31 - 1

 

- 접근방법

 

0. Happy number를 정의하는 프로세스를 살펴보면 일정한 규칙으로 이루어져 있으며,

위 프로세스를 반복할 시 any positive number는 1로 수렴하게 되거나, 혹은 규칙적인 수를 반복하는 루프에 빠지게 된다.

 

 

1. 어떤 양수에 happy number process를 적용하였을때 1이 되지않고 무한루프에 빠지는 경우 무한루프에서 어떻게 빠져나올 수 있을까?

→ 포인터 2개로 플로이드의 토끼와 거북이 알고리즘을 이용한다.

 

1-1 플로이드의 토끼와 거북이 알고리즘이란?

>> 무한루프인 싸이클인지 아닌지 판단하기 위해서 사용한다.

 

-  예를들어 시침은 1~12까지 수로 이루어져있으며, 규칙적인 사이클을 이루고 무한루프이다.

- 1~12중 특정 숫자를 가르키는 포인터 2개를 생성한다.

- 포인터1은 1,2,3,4,5,6,7,8,9,10,11,12,1,2,3,4 ... 순으로 루프를 순회하고 포인터2는 2,4,6,8,10,12,2,4 ... 순으로 순회할때

→ 두포인터는 각각 10번째 수인 10에서 두 포인터는 만난다. (루프에 빠져있다.)

 

 

2. 위 프로세스를 반복 시 포인터가 1이 된다면 true, 루프에 빠져있는 경우를 false를 리턴하면 된다.

 

 

- 코드

class Solution {
    public boolean isHappy(int n) {
        if(happyNumberProcess(n) == 1) return true;

        int ptr1 = n;
        int ptr2 = happyNumberProcess(n);

        while (ptr1 != ptr2) { // 1. is it a loop?
            ptr1 = happyNumberProcess(ptr1);
            ptr2 = happyNumberProcess(happyNumberProcess(ptr2));
        }

        return ptr2 == 1; // 2.
    }

    private int happyNumberProcess (int n) { // happy number process
        int answer = 0;

        while(n > 0) {
            answer += (n%10) * (n%10);
            n /= 10;
        }

        return answer;
    }
}

 

특정 패턴이 반복되는지 판별할 수 있는 플로이드의 토끼와 거북이 알고리즘에 대해 살펴보았다.

 

 

 

 

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

Happy Number - LeetCode