[JS] Happy Number

🔒 문제 (LeetCode 202)

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.

Constraints:

• 1 <= n <= 231 - 1

 

🌊 입출력

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

 

---

 

🔑 해결

🌌 알고리즘

계산하여 1이 되지 않는 수는 사이클을 돌게 되므로 사이클을 저장하는 배열 활용

/**
 * @param {number} n
 * @return {boolean}
 */
var isHappy = function(n) {
    const calculate = (num) => {
        const str = num.toString()
        let total = 0
        for(let i = 0; i < str.length; i++) {
            total += Number(str[i]) * Number(str[i])
        }
        return total
    }
    
    let result = n
    const memo = [n]
    while(result !== 1) {
        result = calculate(result)
        // console.log(result)
        if(memo.includes(result)) {
           break
        } 
        memo.push(result)
    }
    
    return result === 1 ? true : false
};

 

각 digit에 대한 제곱수를 미리 저장하여 활용하는 방법도 있다.

/**
 * @param {number} n
 * @return {boolean}
 */
var isHappy = function(n) {
    const squares = {'0':0, '1':1, '2':4, '3':9, '4':16, '5':25, '6':36, '7':49, '8':64, '9':81}
    
    let set = new Set();
    
    while (!set.has(n)) {
        set.add(n);
        let s = n.toString();
        n = 0;
        for (let i = 0; i < s.length; ++i) {
            n += squares[s[i]];
        }
        if (n == 1) return true;
    }

    return false
};