[LeetCode] 202번 - Happy Number [Java][C++]

문제 링크

---

1. 아이디어

Happy Number인지 판별하는 문제로 Happy Number는 주어진 수의 각 자릿수를 제곱한 후 더해서 나온 수에 대해 다시 같은 과정을 반복할 때 1이 되는 수이다. 수의 변환 과정에서 특정 사이클이 반복되어 Happy Number가 되지 않을 수도 있는데 이를 판별하는 것이 핵심이다.

간단하게는 해시셋을 활용해서 연산 결과가 해시셋에 존재하는 수면 사이클이 발견된 것이므로 Happy Number가 아닌 것으로 판단하는 방법이 있다. 무한 루프 내에서 Happy Number가 되는지 계속 반복하다가 1이 되거나 해시셋에 존재하면 종료하면 된다.

플로이드의 토끼와 거북이 알고리즘을 활용하면 공간복잡도를 줄일 수도 있다. Happy Number인지 판단하는 과정을 연결 리스트에서 노드와 간선을 잇는 과정으로 본다면 Happy Number는 깔끔한 연결 리스트가 되고, Happy Number가 아니면 사이클이 존재하게 된다. 1은 연산을 해도 또 1이 나오므로 토끼와 거북이는 사이클이 존재하는 순간부터 사이클 내부의 어떤 지점에서 결국 만나게 되는데, 이때 만난 값이 1이면 Happy Number이고 그렇지 않으면 Happy Number가 아님을 활용했다.

---

2. 복잡도

1. 해시셋

시간복잡도	공간복잡도
$O(\log n)$	$O(\log n)$

$n$ = 입력 정수

2. 플로이드의 토끼와 거북이 알고리즘

시간복잡도	공간복잡도
$O(\log n)$	$O(1)$

$n$ = 입력 정수

---

3. 코드

1. 해시셋 [Java][C++]

import java.util.*;

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> set = new HashSet<>();

        int res = func(n);
        while (true) {
            if (res == 1) {
                return true;
            } else if (set.contains(res)) {
                return false;
            } else {
                set.add(res);
                res = func(res);
            }
        }
    }

    static int func(int x) {
        int sum = 0;
        while (x > 0) {
            int r = x % 10;
            sum += r * r;
            x /= 10;
        }
        return sum;
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
   public:
    int func(int x) {
        int sum = 0;
        while (x > 0) {
            int r = x % 10;
            sum += r * r;
            x /= 10;
        }
        return sum;
    }

    bool isHappy(int n) {
        unordered_set<int> st;

        int res = func(n);
        while (true) {
            if (res == 1) {
                return true;
            } else if (st.count(res)) {
                return false;
            } else {
                st.insert(res);
                res = func(res);
            }
        }
    }
};

2. 플로이드의 토끼와 거북이 알고리즘 [Java][C++]

class Solution {
    public boolean isHappy(int n) {
        int slow = n;
        int fast = n;

        do {
            slow = func(slow);
            fast = func(func(fast));
        } while (slow != fast);

        return slow == 1;
    }

    static int func(int x) {
        int sum = 0;
        while (x > 0) {
            int r = x % 10;
            sum += r * r;
            x /= 10;
        }
        return sum;
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
   public:
    int func(int x) {
        int sum = 0;
        while (x > 0) {
            int r = x % 10;
            sum += r * r;
            x /= 10;
        }
        return sum;
    }

    bool isHappy(int n) {
        int slow = n;
        int fast = n;

        do {
            slow = func(slow);
            fast = func(func(fast));
        } while (slow != fast);

        return slow == 1;
    }
};

---