LeetCode 202번 - Happy Number

문제 살펴보기

일명 Happy Number를 찾는 문제이다.

 

Happy Number를 찾는 방법은 다음과 같다.

1. 주어진 숫자에서 모든 자릿수의 제곱의 합을 구한다.

2. 제곱의 합이 1이 나올때까지 반복 수행한다.

3. 제곱의 합이 1이 나오면 Happy Number이다.

4. 제곱의 1이 나오지 않으면 1번이 무한히 반복된다.

 

예시) 주어진 숫자가 23인 경우

2^2 + 3^2 = 13

1^2 + 3^2 = 10

1^2 + 0^2 = 1

 

23은 Happy Number

---

생각해보기

숫자가 Happy Number가 아니라면, Happy Number를 찾는 연산이 무한히 반복된다고 한다.

즉, 연산 과정에서 특정한 숫자가 반복해서 얻어지게 된다.

 

예를 들어, 주어진 숫자가 4인 경우

4^2 = 16

1^2 + 6^2 = 37

3^2 + 7^2 = 58

5^2 + 8^2 = 89

8^2 + 9^2 = 145

1^2 + 4^2 + 5^2 = 42

4^2 + 2^2 = 20

2^2 + 0^2 = 4

 

4에서 시작했는데, 연산 도중 4로 돌아왔다.

 

이런 식으로 Happy Number가 아니면 특정 숫자가 반복해서 나온다.

따라서 연산 결과를 따로 모아둔다음, 연산을 할 때마다 연산 결과와 비교해서 반복되는 숫자가 있는지를 확인하면 된다. 

 

---

풀어보기

연산 결과를 저장할 리스트를 만들고, 연산을 수행할 때마다 해당 리스트를 확인하게 했다.

 

만약 리스트에 연산 결과와 같은 숫자가 있으면 Happy Number가 아니므로 반복이 종료되게 했고,

연산 결과와 같은 숫자가 없으면 해당 숫자가 리스트에 저장되게 했다.

 

연산 중 결과가 1이 나오면 Happy Number이므로 반복이 종료된다.

 

boolean flag = true;

List<Integer> calculateList = new ArrayList<>();

while(flag){
    int sum = 0;

    while(n>0){
        sum += (n%10) * (n%10);
        n /= 10;
    }

    n = sum;

    if(n==1) break;

    if(calculateList.contains(n)) {
        flag = false;
    } else {
        calculateList.add(n);
    }
}

return flag;