[Leetcode] 202. Happy Number

Identifying the Problem

happy number 인지 아닌지 판단해 true 혹은 false 값을 리턴한다.

happy number 란 각 자리수 별 제곱해 합하는 과정을 반복하다 보면 1이 되는 값이다.

Organizing thoughts

생각난 방법은 크게 3가지가 있다.

 

첫째 만들어진 모든 수를 배열에 저장하고,

       현재 값이 저장된 배열안에 있는지 판단한다. (중복이면 무한루프가 돌고 있다는 뜻)

 

둘째  만들어진 모든 수를 배열에 저장하고,

        배열을 탐색하는 index의 증가 값을 다르게 해 무한 루프인지 판단하는 방법

 

셋째 모든 값이 37이라는 특정한 값에서 무한루프가 도는 경우가 있는데

       37 loop에 빠지면 false 1이 만들어지면 true 를 리턴한다.

 

생각해본 결과 코드가 가장 간결하고, 복잡하지 않은 세번째 방법이 가장 좋아보였다.

 

1. n이 37이 아니면 루프를 돌게한다.

2. 각 자리별 제곱합을 구한다.

3. n에 제곱합을 대입한다.

4. n이 1이면 true 를 리턴 아니면 계속 루프를 돌게한다.

5. 큰 루프를 빠져나왔다는 뜻은 37이 됐다는 뜻이니 false를 return 한다.

Sourcecode

#include<cmath>

class Solution {
public:
    bool isHappy(int n) 
    {
        int sum = 0;
    
        
        while(n!=37)
        {
            while(n != 0)
            {
                sum += pow(n%10,2);
                n /= 10;
                
                
            }
            
            n = sum;
            if(n==1) return true;
            sum = 0;
        }
        return false;
    }
};

Mistake

새로운 n 마다 sum을 초기화 해줘야하는데 안해서 무한루프가 돎

New things learned

• 코드 관련한 건 아니지만, happy number 가 만들어지는 과정이 신기했다.
  아무리 큰 수더라도 happy number를 만들다 보면 작은 수로 수렴이 되는 것을 확인 할 수 이었다.
  이 작은 수안에서 계속 순환이 이뤄지는 것 같은데 특이점은 37 loop로 가기전에  전조증상으로 4가 나왔다.
  
  
• happy number 인지 판단하는 것과 자리수를 추출하는 과정 때문에 O(n²)가 되는 것은 어쩔 수 없는건가
  pow 함수를 썼으니 O(n³) 인건가?