LeetCode Divide Two Integers (JavaScript), 비트 연산

링크 : https://leetcode.com/problems/divide-two-integers/

문제 설명

Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator.

The integer division should truncate toward zero, which means losing its fractional part. For example, 8.345 would be truncated to 8, and -2.7335 would be truncated to -2.

Return the quotient after dividing dividend by divisor.

Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For this problem, if the quotient is strictly greater than 231 - 1, then return 231 - 1, and if the quotient is strictly less than -231, then return -231.

Example 1:

Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = 3.33333.. which is truncated to 3.

Example 2:

Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7/-3 = -2.33333.. which is truncated to -2.

Constraints:

• 231 <= dividend, divisor <= 231 - 1
• divisor != 0

---

문제 풀이

1. 연산자를 이용해 문제를 접근 -> dividend가 값이 크고, divisor가 값이 작다면 몫을 계산하는데 너무 오래 걸려 시간 초과

2. 1번의 문제를 해결하기 위해 INT_MAX, INT_MIN 상수를 두어 MAX, MIN 값과 -1, 1에 대해 바로 return 할 수 있도록 추가 -> 1에 대해서만 해결, 너무 큰 차이는 시간 초과

3. 비트 연산을 이용해 문제를 해결

---

1. minus : dividend 또는 divisor가 둘 중 하나만 -인 경우에 true

2. divisor가 -1, 1에 대해서는 바로 리턴

3. 1번에서 minus를 구했으니 dividend, divisor은 양수로 수정 (Math.abs -> 절대 값 (양수))

4. dividend >= divisor인 경우 반복문 진행

< 반복문 로직 >

1. tmpDivisor을 두어 << 연사자를 이용해 2의 제곱씩 이동, count의 값(multiple)도 2의 제곱씩 이동

- tmpDivisor가 dividend보다 작은 경우 (즉, 대상보다 나누려는 값이 작은 경우 계속 진행)

- 0보다 큰 경우 진행

ex) 100 / 3인 경우 -> tmpDivisor은 3 -> 6 -> 9 -> 12 -> ... -> 96 이 됨

2. 최종 나누려는 대상을 tmpDivisor로 뺌, answer에 multiple저장

ex) dividend -> 100 - 96 = 4, answer = 32;

이후 한 번더 진행이 가능하고 최종적으로 33이라는 결과를 얻게 됨.

/**
 * @param {number} dividend
 * @param {number} divisor
 * @return {number}
 */
var divide = function(dividend, divisor) {
    const INT_MAX = Math.pow(2, 31) - 1;
    const INT_MIN = -Math.pow(2, 31);
    const minus = (dividend < 0) !== (divisor < 0);

    if (dividend === INT_MIN && divisor === -1) {
        return INT_MAX;
    }
    if (dividend === INT_MIN && divisor === 1) {
        return INT_MIN;
    }

    dividend = Math.abs(dividend);
    divisor = Math.abs(divisor);
    let answer = 0;

    while (dividend >= divisor) {
        let tmpDivisor = divisor;
        let multiple = 1;
        while (dividend >= (tmpDivisor << 1) && (tmpDivisor << 1) > 0) {
            tmpDivisor <<= 1;
            multiple <<= 1;
        }

        dividend -= tmpDivisor;
        answer += multiple;
    }

    return minus ? -answer : answer;
};

---

결론

일반적인 -을 이용해 반복문을 돌리기엔 시간복잡도가 상당히 커질 수 있음

비트 연산자를 활용하여 빠르게 계산이 진행되도록하면 시간복잡도를 줄일 수 있음

 

왜 비트 연산자를 활용하는게 빠른가?

- 일반적인 -은 dividend가 20억이고 divisor가 1인 경우 20억의 뺄셈이 필요 (시간 복잡도 : O(N))

- 비트 연산은 N을 2의 거듭제곱(2^k) 배수만큼 곱하거나 나누는 것과 같음, 또한 비트 연산은 CPU가 가장 빠르게 처리할 수 있는 명령어임 (시간 복잡도 : O(logN))

 

즉, 비트 시프트 연산을 나눗셈에 적용하는 방식은 나눗셈 문제를 이진 탐색 문제로 바꾸어 주어 logN의 시간 복잡도로 해결이 가능