[Leetcode] 202. Happy Number, 350. Intersection of Two Arrays II

202. Happy Number

링크

https://leetcode.com/problems/happy-number/description/

풀이

시간 - 11:29

function sumDigits(num) {
    let sum = 0
    let numStr = num.toString()
    for (let i =0; i<numStr.length; i+=1){
        sum += Number(numStr[i]) *Number(numStr[i])
    }
    return sum
}

var isHappy = function(n) {
    let cnt = 0
    let value = n
    while (cnt < 10000) {
        cnt +=1
        value = sumDigits(value)
        if (value === 1) return true
    }

    return false
};

var calculateSquare = function(num) {
    let sum = 0;
    while (num > 0) {
        let digit = num % 10;
        sum += digit * digit;
        num = Math.floor(num / 10);
    }
    return sum;
};

var isHappy = function(n) {
    let slow = n, fast = n;
    do {
        slow = calculateSquare(slow);
        fast = calculateSquare(calculateSquare(fast));
    } while (slow !== fast);

    return slow === 1;
};

인사이트

1. 생각보다 굉장히 재밌었다. 나는 무식하게 풀어서 사실 틀렸다 보는 게 맞다. 근데, 다른 사람들은 이 문제의 규칙성에 주목했다. 이런 문제의 경우, 반복 또는 규칙성이 있다를 파악한 거 같다. 그래서, two pointer나 set을 이용해서 중복을 체크하는 식으로 문제를 해결하였다. 이 부분은 오히려 알고리즘보다는 퀴즈 같아서 신기했다.

 

 

---

350. Intersection of Two Arrays II (10:09)

링크

https://leetcode.com/problems/happy-number/description/

풀이

시간 - 10:09

var intersect = function(nums1, nums2) {
    const intersection = []
    
    for (let i=0; i<nums1.length; i+=1){
        const idx = nums2.indexOf(nums1[i])
        if (idx !== -1) {
            intersection.push(nums2[idx])
            nums2[idx] = -1
        }
    }

    return intersection
};

var intersect = function(nums1, nums2) {
    nums1.sort((a, b) => a - b);
    nums2.sort((a, b) => a - b);
    
    let i = 0, j = 0;
    const result = [];
    
    while (i < nums1.length && j < nums2.length) {
        if (nums1[i] < nums2[j]) {
            i++;
        } else if (nums1[i] > nums2[j]) {
            j++;
        } else {
            result.push(nums1[i]);
            i++;
            j++;
        }
    }
    
    return result;
};

인사이트

Follow Up 질문들에서 배운 게 많았다.

 

1. What if the given array is already sorted? How would you optimize your algorithm?

=> 정렬이 되어있다면 투 포인터 기법을 사용할 수 있다. 이 부분은 메모리 사용이 적어서 다른 방법보다 좋다.
2. What if nums1's size is small compared to nums2's size? Which algorithm is better?

=> 배열 크기가 작으면 작은 배열을 기준으로, 해시를 쓰는 게 상대적으로 훨씬 유리하다.
3. What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

=> 메모리가 적다면, 청크단위로 이를 반복하는 방법이 있다.