Divide Two Integers | LeetCode 820 | Python3 🐍

 

📄 목차

• 🤔 문제 : Divide Two Integers | LeetCode 820
• 💡 풀이
  • 1. 뺄셈 반복을 통한 몫 구하기
  • 2.  비트연산자 활용

 

 

🤔 문제 : Divide Two Integers | LeetCode 820

문제: https://leetcode.com/explore/interview/card/top-interview-questions-medium/113/math/820/

나눗셈 연산자를 사용하지 않고 나눗셈의 몫을 구하는 문제입니다.

초등학교에서 배운.. 10/3 이라 하면 10-3-3-3.. 해서 양수일 때 까지 뺀 횟수를 구하는 방식이 떠오르네요. 

1번 풀이는 그 풀이에서 반복을 활용하여 연산횟수를 log로 줄이는 방식이고

2번 풀이는 shift연산자를 활용한 풀이입니다. 

 

 

💡 풀이

1. 뺄셈 반복을 통한 몫 구하기

16/2 의 몫을 구한다고 하면 16 - 2- 2 - ....  이렇게 2을 반복하여 빼겠지요?

어차피 2로 반복해서 뺄거라면, 2*2*2 .. 등 2*2^N을 빼서 연산 횟수를 LogN으로 줄일 수 있습니다.

2*2^N를 뺀 후 나머지에 대해서는 또 /2의 를 통해 몫을 구해서 더해줍니다.

 

 

1. 16/2 = 8

    16 - 2 - 2 - 2 - 2 - 2 - 2 - 2 - 2 = 0 

몫 :     +1  +1 +1  +1 +1  +1 +1  +1 = 8  $2^0 * 8$

    16        - 4       - 4       - 4       - 4 = 0

몫 :           +2       +2       +2       +2 = 8  $2^1  * 4$

    16                     - 8                    - 8 = 0 

몫 :                      +4                  +4  = 8 $2^2 * 2$

    16                                               - 16 = 0 

몫 :                                              +8 = 8 $2^3 * 1$

 

 

2. 18/3 = 6

18 - 3 - 3 - 3  - 3 - 3 - 3 =  0  $몫  = 1*6$

18        -6        -6         -6  = 0  $몫 = 2*3$

18                    -12               =6  (몫 = 4*1)

 

18 / 3*2*2 인 12로 나눗셈을 했을 때 나머지 6이 생겼습니다.

이 나머지 6에 대해서는 기존에 나누려는 수 3으로 다시 나눗셈을 해서 몫을 구한 후 더해줍니다.

6 - 3 - 3 = 0 $몫 = 1*2$

6       - 6 = 0 $몫 = 2*1$

최종 몫은 4 + 2 인 6이 됩니다. 

 

 

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        ##   For this problem, if the quotient is strictly greater than 2^31 - 1, then return 231 - 1, and if the quotient is strictly less than -231, then return -2^31.

        # edge case
        if dividend == -2**31 and divisor == -1: return 2**31-1

        # flag if result shuold be negative(-)
        flag = (dividend>0)
        flag = flag if (divisor>0) else not flag

        def dv(dividend, divisor):
            if dividend == 0 : return 0
            if dividend < divisor: return 0

            quotient = 1
            quickDivisor = divisor

            while dividend >= quickDivisor+quickDivisor:
                quickDivisor += quickDivisor
                quotient += quotient
            return quotient + dv(dividend-quickDivisor, divisor)

        ret = dv(abs(dividend), abs(divisor))
        return ret if flag else -ret

 

 

2.  비트연산자 활용

결국 1의 방법은 A/B를 할 때

A를 초과하지 않는 가장 큰 B*2^N로 나눠 몫을 구하고 / 그 몫에는 2^N을 곱해주고 

그 나머지에 대하여  B*2^$N-1$로 나눠 몫을구하고 / 그 몫에는 2^$N-1$을 곱해주고 

..

그 나머지에 대하여  B*2^1 로 나눠 몫을 구하고 / 그 몫에는 2^1을 곱해주고 

그 나머지에 대하여  B*2^0 로 나눠 몫을 구하고 / 그 몫에는 2^0을 곱해주고 

 

하는 방식이죠?

 

B*2^N = B << N 라는 점을 활용하여 비트연산자를 활용한 코드를 짤 수 있습니다.

3 = 11
6 =  3*2 = 110 = 3<<1
12 = 3*2^2 = 1100= 3<<2

 

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        ans = 0
        xx, yy = abs(dividend), abs(divisor)
        for i in range(32, -1, -1):
            if xx >= (yy<<i):
                xx -= (yy<<i)
                ans += (1<<i)
        if (dividend>0 and divisor<0) or (dividend<0 and divisor>0):
            ans = -ans

        return min(2**31-1, max(-2**31, ans))