LeetCode 202 - Happy Number

Happy Number - LeetCode

 

주어진 수 n(1 ≤ n ≤ 2^31 -1)이 happy number라면 true를 반환하라.

happy number는 다음의 과정을 거친다.

1. 임의의 양의 정수로 시작하여, 숫자를 그 숫자의 각 자릿수의 제곱의 합으로 교체한다.
2. 숫자가 1이 될 때까지 또는 1을 포함하지 않은 사이클에서 무한히 반복
3. 이 과정이 1로 끝나는 숫자를 happy number라고 한다.

만약 n = 19 라면 19 → 82 → 68 → 100 → 1 그러므로 true

무한 루프에 빠졌는지 판단이 필요.

무한 루프에 빠졌다는 것은 최초의 상태로 돌아왔다는 뜻이다.

n = 20 이라면 20 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20

값들을 캐싱하고 계산 결과가 캐시에 존재한다면 무한루프가 존재한다는 것이다.

class Solution {
    public boolean isHappy(int n) {
        Set<Long> cache = new HashSet<>();
        
        long num = n;
        while (num != 1) {
            if (cache.contains(num)) return false;
            cache.add(num);
            num = calc(num);
        }
        
        return true;
    }

    private long calc(long num) {
        long sum = 0;
        
        while (num != 0) {
            sum += Math.pow(num % 10, 2);
            num /= 10;
        }
        return sum;
    }
}