[ Top Interview 150 ] 202. Happy Number

문제

202. 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.
  • 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.

  Return true if n is a happy number, and false if not.

• Input : 숫자 n
• Output : n이라는 숫자가 Happy 한가?
• Happy의 기준
  • 특정 숫자(n)에서 시작해서 각 자릿수의 제곱을 하여 모두 더하여 다음 수를 구한다.
  • 특정 횟수를 구하게 되면, 특정 단계로 순환한다.
  • 그 순환에 1이 들어있으면 n을 happy하다고 하고, 그렇지 않으면 happy하지 않다고 한다.

알고리즘 전략

• 다음 숫자 구하는 방법 (각 자릿 수를 따로 구하는 방법)

  • 1번 방법 : 각 숫자를 문자열로 바꾸고 이를 각 문자별로 분해 후 다시 숫자로 바꾸는 방법 (이후 각 자릿수 제곱 후 더함)
  • 2번 방법 : Math.log10()을 이용하여 총 자릿 수를 구하고 이를 $10^i$로 나누고 10 모듈러 연산 사용 (이후 각 자릿수 제곱 후 더함)
  • 자세한 내용은 아래 코드 참고

• 순환 고리를 찾아내는 방법 (자료구조 Set 이용)

  • 맨 처음 수부터 계속 자례대로 나온 수를 Set에 넣음
  • 다음 수를 구했을 때 해당 수가 Set 안에 있는지 확인한다.
    • 있다면 이미 순환이 된다는 의미다.

• Complexity

  • Time complexity : $O(n)$
  • Space complexity: $O(n)$

문제 답안 1 (1번 방법)

• 각 자릿수별로 숫자를 분리할 때, 각 숫자를 문자열로 바꾸고 이를 각 문자별로 분해 후 다시 숫자로 바꾸는 방법

class Solution {

    private static final int HAPPY_TARGET = 1;

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

        int currentNumber = n;
        while (!repository.contains(currentNumber)) {
            repository.add(currentNumber);
            currentNumber = getNextNumber(currentNumber);
        }

        return repository.contains(HAPPY_TARGET);
    }

    private int getNextNumber(int number) {
        char[] numberLetters = String.valueOf(number).toCharArray();

        int sum = 0;
        for (char letter : numberLetters) {
            int value = letter - '0';
            sum += value * value;
        }
        return sum;
    }
}

문제 답안 2 (2번 방법)

• 각 자릿수별로 숫자를 분리할 때, Math.log10()을 이용하여 총 자릿 수를 구하고 이를 $10^i$로 나누고 10 모듈러 연산 사용

class Solution {

    private static final int HAPPY_TARGET = 1;

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

        int currentNumber = n;
        while (!repository.contains(currentNumber)) {
            repository.add(currentNumber);
            currentNumber = getNextNumber(currentNumber);
        }

        return repository.contains(HAPPY_TARGET);
    }

    private int getNextNumber(int number) {
        int size = (int) Math.log10(number) + 1;
        
        int sum = 0;
        for (int i = 0; i < size; i++) {
            int letter = number / (int) Math.pow(10, i) % 10;
            sum += letter * letter;
        }
        
        return sum;
    }
}

각 방법 비교

• 성능 비교

  • 방법 1의 경우, 각 단계마다 String, char[]등의 중간 객체를 필요로 하기 때문에 해당 객체를 생성하는데 시간과 메모리가 꽤 소요됨
  • 방법 2의 경우, 상대적으로 복잡한 수학적 이해를 필요로 하지만, 만들어지는 중간 객체가 없기 때문에 시간과 메모리가 덜 든다.

• 가독성 비교

  • 방법 1의 경우가 훨씬 읽기가 쉬워, 필요시 수정하기가 용이하다.
  • 다음 숫자 만드는 방법이 메서드로 분리되어 있어 해당 기능만 수정하여 사용하기 용이하다.