리트코드 - 202. Happy Number

리트코드 -  202. Happy Number

출처 - https://leetcode.com/problems/happy-number/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

주어진 정수 n이 happy number인지 판별하기 위한 알고리즘을 작성해야 합니다.

happy number는 다음 과정에 따라 정의됩니다:

• 양의 정수로 시작하여, 해당 숫자를 각 자릿수의 제곱의 합으로 대체합니다.
• 숫자가 1이 되면 프로세스를 종료합니다. 숫자가 1이 되면 happy number이거나, 숫자가 1을 포함하지 않는 무한한 반복 사이클에 빠질 수 있습니다.
• 이 프로세스가 1로 끝나는 숫자는 happy number입니다.

 

의사코드

함수 isHappy     sum = 0     calSet = new HashSet     반복문 시작 (n !=1 && calSet에 n이 없는 경우)         calSet에 n 추가         n = calculate(n)     반복문 종료 함수 calculate (int n)     sum = 0     반복문 시작 (n != 0)         number = n % 10         sum += number * number         n /= 10     반복문 종료         sum 리턴

 

풀이코드

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> calSet = new HashSet<>();

        while (n != 1 && !calSet.contains(n)) {
            calSet.add(n);
            n = calculate(n);
        }

        return n == 1;
    }

    static int calculate(int n) {
        int sum = 0;
        while (n != 0) {
            int number = n % 10;
            sum += number * number;
            n /= 10;
        }
        return sum;
    }
}

 

코드설명

간단한 문제이지만 방법을 모르면 어떻게 해결할지 난감한 문제다.

가장 큰 관심사는 계산속에서 무한루프를 끊어낼 수 있는가? 인데...

 

이를 위해서 간단히 2부터 연습을 해보자.

2-> 4-> 16 -> 37(1+36) -> 58(9+49) -> 89(25+64) -> 145(64+81) -> 42(1+16+25) -> 20(16+4)

 

여기까지만 하면 더 할 필요가 없다. 처음의 2의 계산과 같기 때문이다.

계산된 결과는 같은 숫자로 더해진다.

하나 더 3으로 해보자.

 

3 -> 9 -> 81 -> 65 -> 61 -> ...

 

처음 예제에서 진행중에 봤던 16이나 61이나 연산 결과는 똑같으므로 더 할 필요가 없다.

즉, 계산된 값을 set에 추가하여 set에 이미 있다면 루프를 끊어내면 된다.

 

n이 1이 아니거나 set에 포함된 숫자가 아닐때에만 반복문을 돌리고,

최종적으로 n == 1 인지 판단하여 일치하면 true고, 아니면 false를 리턴하면 된다.

 

시간복잡도 - O(log n)

공간복잡도 - O(1) (중간 연산을 계산하는 calSet의 최대크기는 20)

 

문제를 풀며 생각한 흐름과 배운 점

공간복잡도가 숫자에 따라 너무 중구난방이라고 생각되었다.

그래서 문제를 푼 이후 문제 제약조건인 2^31-1 까지를 전부 돌려서 set이 얼만큼 차지하는지 확인해봤는데

연산의 크기가 int의 최대형이니 맥북 프로 M1 인데도 2시간이나 걸렸다.

int max = Integer.MIN_VALUE;;
for (int n = 1; n <= 2147483647; n++){
    System.out.println(n);
    max = Math.max(max, isHappy(n));
}

System.out.println(max);

코드는 대충 이런식으로 돌렸는데, isHappy 메소드가 boolean을 리턴하는게 아니라 set의 size를 리턴하도록 했다.

 

결론적으로 set의 최대크기는 20이므로 공간복잡도는 커봐야 O(1) 인 상수라는 결론을 도달해 낼 수 있었다.

 

수학적으로 뭔가 더 재밌는(?) 것이 있을 것 같은데 왠지 문제를 더 풀다보면 다른 곳에서 나오지 않을까 싶다.

 

정리

무한루프를 끊어내는 조건을 판단하기