[Easy] LeetCode - no.202 Happy Number : Java

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

 

 

문제

숫자 n이 happy number인지 여부 판단

happy number란 각 자리 숫자들을 각각 제곱한 값을 계속 더해가다가 결국 1이 되는 숫자를 말함

Example 1:
Input: n = 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

Example 2:
Input: n = 2
Output: false

 

 

 

풀이1

    public static boolean isHappy(int n) {
        int cnt = 0;

        while (n != 1) {
            int cal = 0;

            String s = "" + n;
            char[] arr = s.toCharArray();

            for (char c : arr) {
                cal += (c - '0') * (c - '0');
            }

            n = cal;
            cnt++;

            if (cnt >= 10) {
                return false;
            }
        }

        return n == 1;
    }

• while문 사용
• n을 String 값으로 변환 후 다시 char 배열로 바꾸어 각각을 제곱하여 더하는 계산을 함
• cnt 변수를 사용하여 while문의 실행 횟수를 카운팅함
  • cnt 변수가 10 이상일 경우 false 반환 (순환이라고 판단, 하지만 10으로 설정한 기준이 없음...)
• n == 1 반환
• 시간복잡도 : O(log N)

💬 어떻게든 통과시켜보려고 막 만든 코드... 통과된 게 신기할 정도

 

 

풀이2

 

    public boolean isHappy2(int n) {
        Set<Integer> set = new HashSet<>();

        while (n != 1) {
            String s = n + "";
            char[] arr = s.toCharArray();
            int cal = 0;

            for (char c : arr) {
                cal += (c - '0') * (c - '0');
            }

            if (set.contains(cal)) {
                return false;
            }

            set.add(cal);

            n = cal;
        }

        return true;
    }

• HashSet 사용
• 계산 과정은 똑같지만 set에 똑같은 계산값이 이미 존재한다면 순환된 것으로 판단하여 false 반환
• 시간복잡도 : O(log N)

💬 조금 더 보완된 풀이지만 여전히 int → String → char[] 의 변환 순서에서 벗어나지 못함

 

 

풀이3

    public static boolean isHappy3(int n) {
        Set<Integer> set = new HashSet<>();

        while (!set.contains(n)) {
            set.add(n);
            n = getNextNumber(n);

            if (n == 1) {
                return true;
            }
        }

        return false;
    }

    private static int getNextNumber(int n) {
        int output = 0;

        while (n > 0) {
            int digit = n % 10;
            output += digit * digit;
            n = n / 10;
        }

        return output;
    }

• HashSet 사용
• 나머지 계산을 사용하여 값을 계산
• 이하 풀이2와 동일
• 시간복잡도 : O(log N)

💬 int → String → char[] 의 변환 순서를 대체할 메서드 작성