LeetCode-202. Happy Number

[Must Do Question - Easy]

How to effectively use LeetCode to prepare for interviews!! - LeetCode Discuss

https://leetcode.com/problems/happy-number/

Happy Number - LeetCode

---

문제

Write an algorithm to determine if a number 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.

Example: 

Input: 19

 

Output: true

Explanation:

1^2 + 9^2 = 82

8^2 + 2^2 = 68

6^2 + 8^2 = 100

1^2 + 0^2 + 0^2 = 1

---

행복한 숫자를 찾는 문제이다.

input 으로 받은 숫자의 자릿수를 제곱하여 더해 나간다.

더한 수가 1이 되면 행복한 숫자가 된다!

 

그렇지 않으면 계속 loop를 돌게 되는데 그건 어떻게 처리해야 될지 생각해봐야겠다.

 

일단 true 로 빠지는 19 예제를 생각하며 짜봤는데 Time Limit Exceeded 가 뜬다.

import java.util.*;
class Solution {
    public boolean isHappy(int n) {
        String number = String.valueOf(n);
        double sum = 0;
        
        while(true){
            for(int i = 0 ; i < number.length() ; i++){
                int num = number.charAt(i);
                sum = sum + Math.pow(num,2);
            }
            if(sum == 1){
                return true;
            }else{
                number = String.valueOf(sum);
            }
        }
    }
}

 

왜 안되지 싶어서 값을 확인 해 보는데 Character에서 int로 자료형이 바뀔때 잘못되는 것 같다.

  System.out.println((int) number.charAt(1)); //9인데 57이 나온다.. 아스키 코드인가

찾아보니 char 을 int 로 하면 아스키 코드값이 나오는게 맞고

 

숫자자체를 쓰려면 뒤에  -'0'을 붙여주면 된다.

 

import java.util.*;
class Solution {
    public boolean isHappy(int n) {
        String number = String.valueOf(n);
        double sum = 0;
        HashSet<Double> set = new HashSet();
 
        
        while(true){
            for(int i = 0 ; i < number.length() ; i++){
                sum = sum + Math.pow(((int) number.charAt(i) - '0'),2);
                System.out.println( (int) number.charAt(i) - '0');
            }
            
            if (sum == 1){
                return true;
            }else{
                if(set.contains(sum)){
                    break;
                }else{
                    set.add(sum);
                    number = String.valueOf(sum);
                    System.out.println("one loop done number : "+number);
                    sum = 0;
                }
            }
        }
        return false;
    }
}

 

이렇게 고쳐도 에러가 난다. 로그를 찍어보면

 

1 9 one loop done number : 82.0 8 2 -2 0 one loop done number : 72.0 7 2 -2 0 one loop done number : 57.0 5 7 -2 0 one loop done number : 78.0 7 8 -2 0 이하 생략

82.0을 number.charAt(i) - '0' 으로 처리하니 8 2 -2 0 으로 출력된다.

 

확실히 자료형을 바꿔가면서 계산하는건 지양해야 겠다.

 

해서 코드를 다시 짜기로 했다.

 

일단 sum이 0되면 true로 while루프가 끝나는 조건이 되는데

 

false일때는 while문 탈출조건을 어떻게 해야할까...

 

Happy number 가 아닌 예제를 만들어 보자

 

23일땐 

23

4+9=13

1+9=10

1+0=1

하필 Happy number 이다.

 

24일땐

24

4+16=20

2+0=2

4    =4

16   =16

-----------------

1+36 =37

9+49=58

25+64=89

64+81=105

1+0+25=26

4+36=40

16+0=16

-----------------

1+36=37

9+49=58

25+64=89

64+81=105

1+0+25=26

4+36=40

16+10=16

-----------------

반복된다.

 

sum으로 나온 값이 이전에 나온 값이면 반복된다고 판단하고 false를 반환하겠다.

 

import java.util.*;
class Solution {
    public boolean isHappy(int n) {
        double sum = 0;
        ArrayList<Double> arraylist = new ArrayList();
        while (true) {
            
            while (n != 0) {
                int num = n % 10;
                //num을 10으로 나눈 값을 다시 num에 저장한다.
                n = n / 10;
                System.out.print(num);
                sum = sum + Math.pow(num, 2);
            }
            System.out.println("\nsum : " + sum);
            if (sum == 1) {
                return true;
            } else {
                if(arraylist.contains(sum)){
                    break;
                }else{
                    arraylist.add(sum);
                    n = (int) sum;
                    sum = 0;
                }
            }
        }//while true
        return false;
    }
}

Success

Details 

Runtime: 36 ms, faster than 5.16% of Java online submissions for Happy Number.

Memory Usage: 39.8 MB, less than 6.06% of Java online submissions for Happy Number.

 

문제자체는 쉬웠지만 sum을 초기화 해주는 것과 같은 걸 빼먹고 Run code를 하는 나를보면

 

어디서 코드짤줄 안다고 말하기 부끄럽다.

 

다른 사람들의 답안에는 ArrayList대신 HashSet을 쓴 답들이 많았다. 

순서는 중요하지 않기 때문에 HashSet을 쓴것 같다.

 

public boolean isHappy(int n) {
    Set<Integer> inLoop = new HashSet<Integer>();
    int squareSum,remain;
	while (inLoop.add(n)) {
		squareSum = 0;
		while (n > 0) {
		    remain = n%10;
			squareSum += remain*remain;
			n /= 10;
		}
		if (squareSum == 1)
			return true;
		else
			n = squareSum;

	}
	return false;

}

 

Absolutely right. In hash set and hash map, Java first use object's hashCode() function to compute the "slot" for the key. If two keys have the same hash code (this is called hash collision and it's actually very rare to happen), they will be compared by using the second key's equals() method, if return true, the two keys are exactly the same, the key will not be added(in set) or its value will be overwritten(in map); if return false, Java will create a linear chain in the slot to store both of them.

 

해석) 해시셋이나 해시맵에서 자바는 hashCode 함수를 통해 key를 위한 슬롯을 계산하고 두 키가 같은 해시코드(해시 충돌-극히 드물게 일어남)이 일어나면 그것들은 두번째 키를 eqauls 함수로 비교된다. 만약 반환값이 true라면 두키는 정확하게 같은거고 키는 set에 추가되지 않거나 (셋에서) 값이 갱신될것이다.(맵에서) false 가 반환되면 Java는 둘다 저장할 선형 제인을 슬롯에 만들 것이다.