202. Happy Number

리트코드 202번 풀이

문제

Happy Number

풀이

아이디어

무한루프가 발생한다는 것은 같은 숫자가 반복적으로 등장한다는 것, 즉 사이클이 발생한다는 것이다. 그래서 Floyd의 사이클 감지 알고리즘(토끼와 거북이)을 활용했다. (참고: 141. Linked List Cycle)

• getNext(n): 각 자릿수의 제곱합을 구하는 함수
• slow: 한 번씩 변환
• fast: 두 번씩 변환

사이클이 있으면 fast === slow가 되고, 행복한 숫자라면 fast가 1에 도달한다.

코드

function isHappy(n: number): boolean {
  function getNext(n: number) {
    let next = 0;

    while (n !== 0) {
      next += (n % 10) ** 2;
      n = Math.floor(n / 10);
    }

    return next;
  }

  let fast = n;
  let slow = n;

  while (fast !== 1) {
    slow = getNext(slow);
    fast = getNext(getNext(fast));
    if (fast === 1 || slow === 1) return true;
    if (fast === slow) return false;
  }

  return true;
}

시간 / 공간 복잡도

• 시간 복잡도: O(log n) — 각 변환 단계에서 자릿수만큼 연산, 사이클은 상수 범위 내에서 발생
• 공간 복잡도: O(1) — 포인터 두 개만 사용