[Leetcode Top Interview 150] 202. Happy Number

난이도 : easy

문제링크

• n이라는 정수가 주어짐
• n이 happy number인지 체크하라
• happy number
  • 양의 정수로 시작하며, 각각의 digit 제곱의 합으로 교체됨
  • 숫자가 1이 될때까지 반복하며, 1이되면 그 숫자는 happy number 이다.

 

1. 접근법

• 각각의 digit 제곱의 합은 10의 멱수가 되어야 한다
• n - digit 제곱합을 해시테이블에 저장한다
• 방문한 n은 다시 방문하지 않는다

 

3. 구현 코드

class Solution {        
    Map<Integer, Integer> map = new HashMap<>();

    public boolean isHappy(int n) {              
        while (n != 1 && !map.containsKey(n)) {
            n = process(n);
        }
        
        return n == 1 ? true : false;
    }

    private int process(int n) {  
        int key = n;
        int num, sum = 0;
        while (n > 0) {
            num = n % 10;
            sum += num * num;
            n /= 10;
        }

        map.put(Integer.valueOf(key), sum);     

        return sum;
    }
}

 

4. 시간복잡도, 공간복잡도 예상

• 시간복잡도 : 불분명 - digit의 합을 계산하는 과정에서 어떤 숫자가 나올 지 모름
• 공간복잡도 : 불분명 - digit의 합을 모두 저장

 

5. 개선점

• 해시테이블이 아닌, set으로 방문점을 보관해서 풀어도 될것 같다

 

6. 회고

class Solution {        
    Set<Integer> visited = new HashSet<>();

    public boolean isHappy(int n) {              
        while (n != 1 && !visited.contains(n)) {
            n = process(n);
        }
        
        return n == 1 ? true : false;
    }

    private int process(int n) {     
        visited.add(n);     
        
        int key = n;
        int num, sum = 0;
        while (n > 0) {
            num = n % 10;
            sum += num * num;
            n /= 10;
        }                

        return sum;
    }
}

(출처 : NeetCode)

• set 자료구조로 방문 숫자를 저장하고 체크해가며 반복문을 돌았다
• 이전의 해시테이블보다 사용성이 적합하고 메모리 측면에서도 효율적이다