[LeetCode] - happy number

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

• Starting with any positive integer, replace the number by the sum of the squares of its digits.
• Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
• Those numbers for which this process ends in 1 are happy.

Return true if n is a happy number, and false if not.

 

양의 정수로 시작하여 숫자를 자릿수 제곱의 합으로 바꿉니다.

숫자가 1이 될 때까지 프로세스를 반복하거나 (유지할 위치) 1을 포함하지 않는주기에서 끝없이 반복됩니다.

1이 되면 행복한 수가 됩니다.

 

 

의사코드

시키는대로 n의 자릿수 제곱의 합이 1이 되면 
return true 아니면 false

1차시도

class Solution {
    public boolean isHappy(int n) {
        if(n == 1) {
            return true;
        }else if(n < 10) {
            return false;
        }
        
        int sum = 0;
        
        while(n > 0){
            sum += Math.pow((n % 10),2);
            n = n / 10;
        }
        
        return isHappy(sum);
        
    }
}

1차 후 생각정리

시키는대로 n의 자릿수 제곱의 합이 1이 되면 
return true 아니면 false
그런데 아니면일 경우가 언제일까
false가 나온 예제 2번을 보자
2
2*2 = 4
4*4 = 16
1*1 + 6*6 = 37
3*3 + 7*7 = 58
5*5 + 8*8 = 89
8*8 + 9*9 = 145
1*1 + 4*4 + 5*5 = 42
4*4 + 2*2 = 20
2*2 + 0*0 = 4
.... loop를 돈다
즉 나왔던 수를 저장하고 check해야 함

 

2차 시도

class Solution {
    public boolean isHappy(int n) {
        ArrayList<Integer> arr = new ArrayList<>();
        arr.add(n);
        
        while(n != 1){
            n = getprocessingNumber(n);
            if(arr.contains(n)) {
                return false;
            }
            else{
                arr.add(n);
            }
        }
        
        return true;
    }
    
    public int getprocessingNumber (int n){
        int number = 0;
        
        while(n > 0){
            number += Math.pow((n % 10),2);
            n = n / 10;
        }
        return number;
    }
}

Runtime: 1 ms, faster than 81.05% of Java online submissions for Happy Number.
Memory Usage: 36 MB, less than 45.07% of Java online submissions for Happy Number.

풀긴 풀었는데 삽입과 검색이 둘 다 잦아서 ArrayList외에 어떤 자료구조를 쓰면 효율적일지가 궁금하다.

 

1이 아니면 행복하지 않다 1이 될때까지 갈아버리다가 결과가 전에 했던것과 같으면 결국 불행하다는건 뭔가 슬프다.