202. Happy Number

문제

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

내 코드

1차 코드 (시간복잡도 O(N), 공간복잡도 O(N))

import java.util.*;

class Solution {

    public int makeSum(int n){
        int tmp = n;
        int sum = 0;
        while(tmp != 0){
            int rem = tmp%10;
            sum += (rem*rem);
            tmp/=10;
        }
        return sum;
    }

    public boolean isHappy(int n) {
        Set<Integer> s = new HashSet<>();
        int curNum = n;
        while(true){
            if(s.contains(curNum))
                break;
            s.add(curNum);
            curNum = makeSum(curNum);
            if(curNum == 1)
                return true;
        }
        return false;
    }
}

그냥 set으로 history를 저장해줌. 직관적인 생각이었다.

2차 코드 (시간복잡도 O(N), 공간복잡도 O(1))

import java.util.*;

class Solution {

    public int makeSum(int n){
        int tmp = n;
        int sum = 0;
        while(tmp != 0){
            int rem = tmp%10;
            sum += (rem*rem);
            tmp/=10;
        }
        return sum;
    }

    public boolean isHappy(int n) {
        //무한루프는 회기한다. 
        //slow는 한 칸씩, fast는 두 칸씩 회기하다 보면
        //언젠가는 만날 것이다. - floyd cycle detection
        int slow, fast;
        slow = fast = n;
        do {
            slow = makeSum(slow);
            fast = makeSum(makeSum(fast));
        }while(slow != fast);
        if(slow == 1) return true;
        return false;
    }
}

대충, 무한루프를 돌면 한 칸씩 움직이는 slow와 두 칸씩 움직이는 fast가 언젠가는 만날 것이고, 1로 끝나면 결국 둘다 1에서 만날 것이다.
이는 플로이드 순환 찾기 알고리즘의 내용이다.
https://snutiise.github.io/Floyd's-Cycle-Detection-Algorithm/