LEETCODE 29. 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: [−2^31, 2^31 − 1]. For this problem, if the quotient is strictly greater than 2^31 - 1, then return 2^31 - 1, and if the quotient is strictly less than -2^31, then return -2^31.

나눌 숫자와 나누는 숫자가 주어진다. 나눗셈, 곱셈, 나머지 연산을 하지 않고 값을 구하자. 보통은 내림처리를 할 것이다. 8.345는 8, -2.7335는 -2로 답을 나오도록 한다. 나눈 몫을 반환하면 된다.

참고로, 2^31 - 1을 넘거나 -2^31 을 넘으면 해당 값에 제일 가까운 제한 값을 반환하면 된다.

---

이건 비트 연산이 필요했다. 처음엔 어 곱셈 안되고 나눗셈 안되면 걍 무식하게 빼라는거 아냐~ 하고 만들었는데, 시간 초과가 뜨는걸보고 아 뭔가 접근부터 망했구나 싶어서 곰곰히 생각해보니 비트 연산이 생각났다. 비트 연산도 큰 틀로 보면 곱셈의 영역이라서 하면 안되는 줄 알고 생각을 떠올리지도 않았는데 아쉽다.

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        if(dividend <= -2147483648 and divisor == -1): return 2147483647
        isNegative = (dividend < 0) ^ (divisor < 0)
        dividend = abs(dividend)
        divisor = abs(divisor)

        if dividend < divisor:
            return 0

        quotient = 0

        while dividend >= divisor:

            k = 0
            while (divisor << (k + 1)) <= dividend:
                k += 1

            dividend = dividend - (divisor << k)
            quotient = quotient + (1 << k)

        if isNegative:
            return -quotient
        else:
            return quotient