algorithm

[Algorithm] LeetCode 202.happy number using HashSet

tonirr 2020. 5. 18. 00:41 

class Solution {
    public boolean isHappy(int a) {
        String n = Integer.toString(a);
        boolean isHappyNum = false;

        int sum = 0;
        char[] array = n.toCharArray();

        for(int i = 0; i < array.length; i++){
            int ans = Integer.parseInt(Character.toString(array[i]));
            sum += ans*ans;
        }

        int sum1 = 0;
        int j = 0;
        while(sum1 != 1){
            String sumToStr = "";

            if(j == 0){
                sumToStr = Integer.toString(sum);
            } else{
                sumToStr = Integer.toString(sum1);
            }
            j++;
            char[] array1 = sumToStr.toCharArray();

            sum1 = 0;
            for(int i = 0; i < array1.length; i++){
                int ans = Integer.parseInt(Character.toString(array1[i]));
                sum1 += ans*ans;
                if(sum1 == 1){
                    isHappyNum = true;
                }
            }
        }
        return isHappyNum;
    }
}

원래 코드.. 굉장히 억지로 풀었고 시간초과도 났다. 아직 자료구조가 많이 부족한 듯 싶다.

아래는 LinkedHashSet 으로 푼것

  • hashSet에 있는 contains함수를 사용해서 때마다 더해지는 sum을 n에 넣고 hashSet에 n을 저장한다.
    • hashSet.contains(n)의 Big-O는 O(1)이다.
  • n을 10으로 나눠서 나머지를 구하면 1의 자리부터 숫자를 분리할 수 있다.
    • 예를들어 379라면 
      • 첫번째에는 9
      • 두번째에는 7
      • 세번째에는 3
      • 네번째 돌때에는 3을 10으로 나누면 0이 나오므로 n > 0 조건을 만족하지 않아 루프가 끝난다.
    • 숫자를 분리해서 제곱해서 sum에 더하고
    • n을 10으로 나눈 값을 n에 넣는다.
    • 나눠서 0이 되면 n에 sum을 대입하고 리턴한다.
  • 만약 제곱해서 더한 값이 1이 나오고 다음 루프를 돈다면 1이 이미 hashSet에 들어있으므로 hashSet.contains(n)의 조건에 만족한다.
    • 루프에서 나오고 n == 1(true)값을 리턴한다.
class Solution {
    public boolean isHappy(int n) {
        HashSet<Integer> hashSet = new LinkedHashSet<>();
        while(!hashSet.contains(n)) {
            hashSet.add(n);
            int sum = 0;
            while(n > 0){
                sum += (n % 10) * (n % 10);
                n /= 10;
            }
            n = sum;
        }
        return n == 1;
    }
}