[Algorithm] LeetCode 202.happy number using HashSet

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;
    }
}

 

• 기억할 것들
  • LinkedHashSet과 HashSet의 차이
    •  LinkedHashSet은 순서를 고려하고 HashSet은 순서를 고려하지 않는다.
  • LinkedHashSet에서 contains메소드로 해당 요소를 찾을 때 Big-O는 O(1)이다.
    • https://stackoverflow.com/questions/559839/big-o-summary-for-java-collections-framework-implementations