[LeetCode] 29. Divide Two Integers

---

카테고리 : Bit Manipulation
난이도 : Medium

---

2022/5/30 (월) 문제.

Divide Two Integers - LeetCode

아이디어

dividend와 divisor가 주어지고, 곱하기 연산자(*), 나누기 연산자(/), 나머지 연산자(%)를 사용하지 않고 두 정수를 나눠야 한다.

 

두 정수를 나눈 몫을 구해야 한다. 이때 정수를 제외한 소수 부분은 제외한다.

 

이 문제를 딱 보고 든 생각은

 

곱셈, 나눗셈, 나머지 연산자를 사용하지 않으면서 몫을 구한다 => 비트 연산자를 사용해야 하는구나

 

였다.

 

---

 

핵심 아이디어는 이렇다. 우리가 나눗셈을 할 때 몫을 구하는 건 나눠지는 수에서 나누는 수를 얼마나 뺄 수 있는지 그 횟수를 구하는 것과 같다.

dividend가 30, divisor가 2라고 생각해보자. 2를 최대 15번 뺄 수 있다. 2를 16번을 빼면 -2가 되기 때문에 이는 몫을 틀리게 구한 것이 된다.

dividend가 30, divisor가 4일 때도 마찬가지다. 4를 최대 7번 뺄 수 있는데, 4를 8번 빼면 -2가 되기 때문에 몫을 잘못 구한 것이다.

 

따라서 나눠지는 수에서 나누는 수를 최대 얼마나 뺄 수 있는지 횟수를 비트연산자를 사용해서 구하면 된다.

 

dividend가 30, divisor가 2인 경우를 생각해보자.

 

30 / 2 => 2가 30보다 작거나 같기 때문에, 30에서 2를 뺄 수 있다는 것을 알 수 있다. 그렇다면 2를 증가시켰을 때도 30으로 나눌 수 있는지를 확인한다.

 

2에 shift left 연산(<<)을 해서 4로 증가시켰다. 참고로 shift left 연산을 하면 비트를 왼쪽으로 한 칸씩 미니 2를 곱한 효과가 난다.

 

30 / 4 => 4도 마찬가지로 30보다 작거나 같기 때문에 30을 4로 뺄 수 있다는 것을 알 수 있다.

그렇다면 뺄 수를 어디까지 증가시킬 수 있을까? 빼는 수가 30보다 커지는 순간 뺄 수 없기 때문에 우리는 뺄 수를 16까지만 증가할 수 있다는 것을 알 수 있다.

핵심은 30에서 뺄 수 있는 가장 큰 수를 찾는 것이다. 이 과정에서 divisor는 총 몇 번 빠졌는지 같이 확인해보자.

• 만약 빼는 수가 2라면 divisor를 뺀 횟수는 1회가 된다.
• 만약 빼는 수가 4라면 divisor를 뺀 횟수는 2회가 된다.
• 만약 빼는 수가 8이라면 divisor를 뺀 횟수는 4회가 된다.
• 만약 빼는 수가 16이라면 divisor를 뺀 횟수는 8회가 된다.

 

이는 당연한 건데, 빼야 하는 수가 매번 2배가 되니 이에 따라 빼게 되는 횟수도 2배가 되는 것이다. 따라서 30에서 16을 빼게 되면 14가 남고, 지금까지 divisor 2를 총 8회 뺀 걸 알게 된다.

 

이제 나머지 14에 대해서도 똑같은 과정을 반복한다. 14에서 뺄 수 있는 가장 큰 수는 8, 뺀 횟수는 이전에 뺀 횟수 8회에 새로 뺀 횟수 4회를 더해 12번이 된다. 남은 수는 14 - 8 인 6이 된다.

 

이런식으로 남은 수가 divisor보다 크거나 같을때까지 계속 같은 과정을 반복한다. 만약 남은 수가 divisor보다 작으면 divisor로 뺄 수 없기 때문이다.

코드

위에서 생각한 걸 코드로 옮겨봤다.

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        # overflow에 대한 예외 처리를 해준다
        if (dividend == -2147483648 and divisor == -1): 
            return 2147483647

        # dividend, divisor의 부호에 따라 정해지는 몫의 부호가 된다.
        multiplier = 1

        # dividend, divisor를 모두 계산하기 편하게 양수로 바꿨다.
        if dividend < 0:
            dividend = -dividend
            multiplier = -multiplier
        if divisor < 0:
            divisor = -divisor
            multiplier = -multiplier

        # 남은 빼야 할 수
        left = dividend
        # 몫
        quotient = 0

        # 남은 수가 divisor보다 크거나 같을 때만 계속 반복할 수 있다.
        while left >= divisor:
            # 내부 while loop에서 사용할 임시 몫(divisor를 빼는 횟수)이다. 
            temporalQuotient = 1
            # 빼게 될 수다. 우리의 목표는 이 currentNumber의 최댓값을 구하는 것이다.
            currentNumber = divisor
            # 빼야 할 최대 수를 구한다.
            while True:
                nextNumber = currentNumber << 1

                # 뺄 수가 남은 수보다 작거나 같으면 뺄 수 있다
                if nextNumber <= left:
                    # 빼는 횟수, 뺄 수를 모두 두 배로 만든다.
                    temporalQuotient = temporalQuotient << 1
                    currentNumber = nextNumber
                # 만약 빼야 할 수가 남은 수보다 더 커지게 되면 진행 할 수 없다.
                else:
                    left -= currentNumber
                    quotient += temporalQuotient
                    break

        return quotient * multiplier