[Leetcode] 202. Happy Number - JS

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

 

1. 문제 분석

문제분석
--------------------
- 숫자 n이 'happy'한지 판단하라.
- 'happy' 숫자는 아래 과정으로 판단한다.
    - 양의 정수로 시작하고 각 자릿수의 제곱의 합으로 숫자를 바꾼다.
    - 위 과정을 1이 될 때까지 반복한다.
- 1이 되면 이 숫자는 'happy' 한 숫자이다.

제한조건
--------------------
- 1 <= n <= 2^31 - 1

 

2. 접근 방법

접근방법
--------------------
각 자릿수 0~9의 제곱을 최적화하기 위해 hash에 추가한다.
n이 1이 될 때 까지 반복한다.
내부 반복문 안에서 n의 각 자릿수를 hash에 대입하여 sum을 구한다.
sum이 이전에 등장했는지 체크하여 등장했다면 무한 반복되므로 false를 반환한다.
n을 sum으로 재할당하여 반복한다.

 

 

3. 코드

var isHappy = function(n) {
    const hash = {
        0: 0,
        1: 1,
        2: 4,
        3: 9,
        4: 16,
        5: 25,
        6: 36,
        7: 49,
        8: 64,
        9: 81
    };
    const seen = new Set();

    while (n !== 1) {
        let current = n;
        let sum = 0;

        while (current > 0) {
            let digit = current % 10
            sum += hash[digit]
            current = Math.floor(current / 10)
        }

        if (seen.has(sum)) {
            return false
        }

        seen.add(sum)
        n = sum
    }
    return true;
};

 

 

4. 복잡도 분석

- 시간복잡도: O(log n)

- 공간복잡도: O(1)

 

문제의 설명이 구체적이지 않아 제대로 이해를 못했다. 문제를 이해하니 푸는 것은 간단했다.

숫자의 자릿수를 모두 더하는 로직이 익숙하지 않았는데, 이번 문제를 통해 익숙하게 할 수 있게 되었다.

이미 등장했던 요소인지 아닌지는 새로운 객체 해쉬맵을 사용해도 되지만, 기존 hash와 구분하기 위해

Set() 자료구조를 사용했다.

 

각 자릿수의 제곱의 합으로 반복해주니 n 보다 더 빠른 log n의 시간복잡도를 가지는 것도 알게되었다.