[Leetcode][Python] 29. Divide Two Integers 3Sum

리트코드 / 파이썬 / 29. Divide Two Integers 3Sum

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

Divide Two Integers - LeetCode

풀이 방법

이 문제의 핵심은 두가지다.

 

1. 32bit singed integer([-2**31, 2**31 + 1]만 저장할 수 있고, division 결과가 overflow인 경우 2**31 - 1을 반환해야 한다.
   이 경우에 해당하는 것은 딱 한 가지밖에 없다. --> dividend == -2**31이고, divisor == -1인 경우
   
   
2. 비트 연산 활용
   가장 간단한 방법은 dividend에서 divisor를 계속 빼주는 방법이지만, time out이 난다.

최적의 방법은  divisor * 2^N를 dividend에서 빼면서 줄여나가는 것이다.

모든 수는 아래와 같이 표현할 수 있다. 

 

 

 

위에서 얘기한 비트 연산을 활용하기 위해, 그리고 모든 양의 정수는 위의 식과 같이 표현이 가능하기 때문에

아래 그림의 예시와 같이 process를 진행한다. 

 

 

 

 

비트 연산으로 dividend를 넘지 않는 divisor * 2^N을 구해 몫을 더해나간다.

 

 

복잡도는,

​-> O(logN)

 

 

소스 코드

class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        quotient = 0
        sign = 1

        if dividend * divisor < 0:
            sign = -1

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

        dividend = abs(dividend)
        divisor = abs(divisor)

        while dividend - divisor >= 0:
            x = 0
            while dividend - (divisor << 1 << x) > 0:
                x += 1
            dividend -= (divisor << x)
            quotient += (2 ** x)

        quotient *= sign

        return quotient