[SQL] LeetCode 202번 문제 학습

문제 설명

Happy Number는 주어진 숫자가 "행복한 숫자"인지 판별하는 문제임. 행복한 숫자는 각 자릿수의 제곱을 더하는 과정을 반복해서 결국 1이 되는 숫자

• n = 19:
  • 1² + 9² = 1 + 81 = 82
  • 8² + 2² = 64 + 4 = 68
  • 6² + 8² = 36 + 64 = 100
  • 1² + 0² + 0² = 1
  • 1이 됐으니까 19는 행복한 숫자
• 반면, 1이 안 되면 무한 루프에 빠짐 (예: n = 2는 계속 다른 숫자 나옴).

제약 조건:

• 입력 n은 양의 정수.
• 행복한 숫자면 true, 아니면 false 리턴.
• 무한 루프를 피하려면 사이클을 감지해야 함.

문제를 푼 과정

재귀 방식으로 풀었음

1. 기저 사례 (Base Case)
   • 입력 n이 한 자릿수(n <= 9)일 때 처리.
   • 한 자릿수 중 행복한 숫자는 1과 7뿐임 (직접 계산해보면 7은 7² = 49 → 4² + 9² = 97 → 9² + 7² = 130 → 1² + 3² = 10 → 1² = 1).
   • 그래서 n == 1 || n == 7이면 true, 나머지 한 자릿수는 false.
   • 이 조건으로 재귀가 너무 깊어지는 거 방지함.
2. 자릿수 제곱 합 계산
   • n이 한 자릿수 아니면, 각 자릿수의 제곱을 더함.
   • for n > 0 루프에서:
     • tmp = n % 10: 마지막 자릿수 뽑음.
     • sum += tmp * tmp: 자릿수 제곱해서 sum에 추가.
     • n /= 10: 다음 자릿수로 이동.
   • 예: n = 19면, 9² + 1² = 81 + 1 = 82.
3. 재귀 호출
   • 계산한 sum으로 isHappy(sum) 재귀 호출.
   • 이 과정을 반복해서 sum이 1이 되면 true, 아니면 계속 돌다가 한 자릿수 케이스에서 false 나옴.

---

어떤 알고리즘 썼는지

이 문제는 재귀(Recursion)랑 수학적 계산 썼음

1. 재귀
   • 자릿수 제곱 합을 구하고, 그 결과로 다시 함수 호출.
   • 기저 사례로 한 자릿수 처리해서 재귀 깊이 제한.
   • 시간복잡도는 정확히 계산하기 어렵지만, 행복한 숫자는 보통 빠르게 1로 수렴하고, 아닌 숫자는 사이클에 갇힘.
   • 공간복잡도: O(log n) (재귀 스택 깊이, 숫자 크기에 따라).
2. 자릿수 처리
   • 10으로 나눠가며 자릿수 뽑는 기본 수학 연산.
   • 각 자릿수 제곱 합 구하는 건 O(log n) (자릿수 개수만큼).

문제는 사이클 감지가 없음. 행복한 숫자가 아닌 경우(예: n = 2) 무한히 돌 가능성이 있는데, 코드가 한 자릿수 케이스로 빠져나가서 우연히 동작한 듯. 해시셋이나 Floyd의 사이클 감지 알고리즘으로 사이클 체크하면 더 안전함.

 

package main

import (
	"os"
	"fmt"
)

func isHappy(n int) bool {
	if n <= 9 {
		if n == 1 || n == 7 {
			return true
		}
		return false
	}

	sum := 0
	tmp := 0
	for n > 0 {
		fmt.Fprintln(os.Stderr, n)
		tmp = n % 10

		sum += tmp * tmp

		n /= 10

	}

	return isHappy(sum)
}

func main() {
	fmt.Fprintln(os.Stderr, isHappy(19))
}