[LeetCode] Java - Happy Number

 

 

LeetCode 30일 챌린지 2일차는 Happy Number가 출제 되었습니다.

 

문제 난이도는 easy에요.

 

문제는 주어진 숫자를 자리수마다 제곱하여 더하고 그 수가 만약 1로 수렴한다면 Happy Number 이다. 라는 문제입니다. 생각보다 어렵지 않은 문제라고 생각되어 아래와 같이 작성하여 제출했습니다.

 

class Solution {
    public boolean isHappy(int n) {
    	boolean result = true;
    	HashSet<Integer> hs = new HashSet<Integer>();
    	hs.add(n);
    	int num;
    	while(true) {
    		if(n == 1) break;
    		num = 0;
    		while(n != 0) {
    			num += (n%10) * (n%10);
    			n = n/10;
    		}	
    		n = num;
    		if(hs.contains(n)) {
    			result = false;
    			break;
    		}
    		hs.add(n);
    	} 	
        return result;
    }
}

숫자를 제곱하는 것은 반복문으로 처리하였고 무한 루프가 발생하는 시점을 새로운 숫자를 만들었을때 기존의 있던 숫자라면 무한 루프가 발생한다고 보았습니다.

 

그래서 HashSet에 생성된 숫자들을 넣어서 판별했습니다.

 

코드를 제출하고 결과를 보니 1ms 정도 수행되더라구요.

하지만 최적의 소스코드는 아니였습니다.

 

10%정도 안에 들어가는 코드는 0ms가 되더군요.

오늘도 Solution을 보면서 어떻게 고쳐야 할지 판단해보았습니다. 

 

class Solution {
    public boolean isHappy(int n) {
        int slow = n;
        int fast = n;
        
        do {
            slow = HappySq(slow);
            fast = HappySq(HappySq(fast));
        } while (slow!=fast);
        return slow == 1? true: false;
    }
    
    private int HappySq(int n) {
        int num = 0;
        while(n != 0) {
            num = num + (n%10) * (n%10);
            n= n/10;
        }
        return num;
    }
}

 

slow와 fast를 선언하고 slow는 한번, fast는 두번 실행해서 서로를 비교해 숫자가 같아지면 빠져나오도록 하는 코드입니다. 처음에는 이렇게 하면 왜 반복되는 숫자 판별이 될까 라는 고민을 했는데. 아직 머리에 확실히 들어오지는 않네요.

 

좀더 고민을 해봐야겠습니다.

이정도의 코드를 생각해야 상위 11%정도에 들어가는 문제 같아요.

 

더 공부를 해야겠네요. ㅎㅎ

 

오늘의 도전은 여기까지!