LeetCode[day2] - 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, and 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 numbers.
Return True if n is a happy number, and False if not.

Input: 19 Output: true Explanation: 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1

 

1. 알고리즘을 해결하기 위해서 생각한 방법

 

 내가 처음에 알고리즘을 풀기 위해서 접근한 방법은 아래와 같다.

 - happy number란 무엇인가?

 - n이라는 숫자가 있을 때, 어떻게 자릿수를 얻을 수 있을까?

 - n이라는 숫자가 이미 나왔다면, 어떻게 처리해야할까?

 이와 같이 3가지 방법을 고민하게 되었다.

 

2. 알고리즘 작성 중에 어려웠던 점

 

 - happy number의 조건은 무엇일까? (여기까지는 쉬웠음)

  우선, happy number인지 확인하는 조건은 각 자릿수의 값의 제곱의 합이 1이어야 한다. 그렇지 않다면, 제곱의 합에서 나온 결과에 대한, 값을 다시 체크한다. 만약 제곱의 합을 통해서 나온 결과가 이전에 나온 값이라면, 그 값은 happy number가 아니다. 

 그렇기 때문에 happy number는 체크하기 하나의 숫자만 1이어야 한다. 그렇게 됐을 때, happy number는 100000, 1000, 100, 1 이와 같은 결과일 것이다.

 - 각 자리수의 합을 구하는 방법?

 우선, 내가 작성한 각 자릿수를 구하는 방법은 해당 값을 String으로 변경하고 split한 후, 나오는 String 배열을 통해서 다시 integer로 변경하는 방법을 생각했다. 여기서 보면, String이 String[]이 되고, 각 값들의 String이 다시 Integer가 되므로 구린냄새가 난다.

 - 내가 만든 happy number을 판별하는 방법?

 happy number는 가장 큰 자릿수가 1이고, 그 외에는 0의 값만 있어야 한다. 그렇기 때문에, 만약 검사해야하는 happy number가 101이라면, 101 - 100 과 같은 알고리즘이 필요했다. 생각한 방법은 101 % 100, 과 같이 나머지 연산자를 통해서 0인지 아닌지 체크하는 방법이었다. 하지만, 여기에서도 구린내가 난다.

 - 이미 검사한 happy number인 숫자?

 내가 검사하려는 happy number가 이미 앞에서 검사한 조건인지, 확인하기 위해서 가장 쉽게 접근할 수 있는 List를 사용했다. 그래서 contains() 메소드를 통해서 값을 체크해줬다.

 

3. 알고리즘 작성

 

public boolean isHappy(int n) {
    boolean isHappyNumber = false;
    String happyNumber = String.valueOf(n);
    
    //이미 있는 값인지 확인하기 위한 변수
    List<Double> cache = new ArrayList<>();
    while(true){
        String[] splits = happyNumber.split("");//각 자릿수를 구하기 위한 방법
        double sum = 0;
        for(String s : splits){
            Integer intValue = Integer.valueOf(s);
            sum += Math.pow(intValue,2);//모든 값들의 제곱의 합
        }
        if(cache.contains(sum)){//값이 있는 지 확인
            break;
        }
        cache.add(sum);//값 추가
        //happy number는 1이거나, happynumber는 10의 문자열 길이의 제곱의 나머지가 없어야한다.
        if(sum == 1 || sum % Math.pow(10, String.valueOf(sum).length()) == 0){
            isHappyNumber = true;
            break;
        }
        happyNumber = String.valueOf((int)sum);
    }    
    return isHappyNumber;
}

4. 결과

 구리다 구려. 저기 밑에서 5.49프로가 내가 작성한 방법이다. 위의 방법은 절대 하면 안된다.

5. 다른 사람이 작성한 알고리즘 보기

 

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> cache = new HashSet();//Set을 통해서 중복된 값들은 자동으로 제거
        while(!cache.contains(n)){
            cache.add(n);
            n = getSum(n);
            
            if(n == 1){
                return true;
            }
        }
        return false;
    }
    
    public int getSum(int num){
        int sum = 0;
        while(num > 0){
            //num > 0보다 클 때까지,
            //num이 19라면,
            //19 -> 19 % 10 = 9, 9 * 9, 1의 자릿수
            //19 / 10, 1 * 1; 10의 자릿수
            //81 + 1;
            //82 -> 82 % 10 = 2, 2 * 2, 1의 자릿수
            //82 / 10 = 8, 8 * 8
            //4 + 64 
            //68 -> 68 % 10 = 8, 8 * 8
            //68 / 10 = 6, 6 * 6
            //100, 100 % 10 = 0, 0*0,
            //10, 10 % 10 = 0, 0*0,
            //1, 1 % 10 =1 , 1 * 1
            //1로 떨어짐
            sum += (num % 10) * (num % 10);
            num /= 10;
        }
        return sum;
    }
}

 

6. 다른 사람이 작성한 알고리즘으로 배운 점

 

 - 각 자리수의 합을 구하는 방법

 각 자리의 합을 구하는 방법은 n % 10을 통해서, 해당 자리수의 숫자를 구할 수 있다. 그리고, 다시 10으로 나눠서, 다음 자릿수로 이동할 수 있다. 너무 완벽하당...

 - happy number인지 확인하는 방법

 단순히, sum을 통해서 나머지의 제곱을 누적해주면 된다.

 - 이미 검사한 happy number 숫자

 단순히 contains()라는 메소드를 사용해서 List를 생각했었는데, 해당 알고리즘은 Set을 사용했다. Set을 사용했을 때, 이점은 무엇일까 검색을 해봤다.

 List에서 cotains은 O(n)이고, HashSet에서 contains는 O(1)이다. List는 많으면 많을 수록 증가하고, Set은 항상 1이다. 메모리 측면에서도 효율적이라고 한다.

 

7. 반성해야할 점

 

 - 자료구조를 선택하는 것에 있어, 지식을 넓혀나가야 한다.

 List vs Set과 같이 메소드를 하나 사용하는 것에 있어 효율이 다르다는 것을 명심하자.

 - 각 자릿수, 문자를 하나씩과 같을 때, 항상 splits 메소드를 쓰지는 말자.

 더 좋은 방법은 자릿 수, 해당 번 째 문자를 구하는 방법은 존재할 것이다.

 

- 문제 : https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/528/week-1/3284/

Explore - LeetCode

- HashSet vs List : https://stackoverflow.com/questions/150750/hashset-vs-list-performance

HashSet vs. List performance

- 참고한 알고리즘 사이트 : https://www.programcreek.com/2014/04/leetcode-happy-number-java/

LeetCode – Happy Number (Java)