๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

์•Œ๊ณ ๋ฆฌ์ฆ˜/LEETCODE

Divide Two Integers | LeetCode 820 | Python3 ๐Ÿ

๋ฐ˜์‘ํ˜•

 

๐Ÿ“„ ๋ชฉ์ฐจ

     

     

    ๐Ÿค” ๋ฌธ์ œ : 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))

     

    ๋ฐ˜์‘ํ˜•