29. Divide Two Integers

[zeikar]

Problem link

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

Problem Summary

두 정수를 곱하기, 나누기 연산 없이 나눈 몫을 구하는 문제.

Solution

뭔가 쉬워 보이는데 어려운 문제이다.
일단 나누기를 다시 생각해보면 여러 번 뺀다고 생각할 수 있다. 즉, 10/3 은 10을 3으로 3번 뺄 수 있으므로 답이 3이 나오게 된다.
하지만 빼는 것을 하나씩 다 하면 시간 초과가 난다. 더 빨리 뺄 수 있는 방법을 찾아야 하는데 이것이 비트 시프트 연산이다.

3을 비트 시프트로 왼쪽으로 1 이동시키면 2배인 6이 되고 한 번 더 이동시키면 12가 된다. 이런 식으로 dividend보다 작을 때 반복해주면서 빼주면 된다. 남은 값은 다시 한 번 시프트 연산하면서 divisor보다 작아질 때까지 빼주면 된다.

기타 부호 같은 자잘한 것들은 미리 처리하여 주었다.

Source Code

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        sign = 1
        if (dividend < 0) ^ (divisor < 0):
            sign = -1
        
        dividend, divisor = abs(dividend), abs(divisor)

        quotient = 0
        while dividend >= divisor:
            d = divisor
            cnt = 1
            while dividend >= (d << 1):
                d <<= 1
                cnt <<= 1
            
            dividend -= d
            quotient += cnt
        
        return min(sign * quotient, (1 << 31) - 1)