[LeetCode # 29] Divide Two Integers

두 수 dividend, divisor 가 주어졌을 때 dividend 를 divisor 로 나눈 몫을 구하는 문제

 

몫을 구하는 문제이기 때문에 나눗셈을 수행하지 않고, 뺄셈으로 나눗셈을 구현하는 방법을 생각해 보았다.

예를 들어, 10 을 3으로 나누면 10 / 3 = 3.333... 이지만 몫만 구할 경우 10 = 3 x 3 이므로 10 = 3 x (2 + 1) 로 표현이 가능하다. 마찬가지로 72 를 7로 나누면 72 / 7 = 10 (몫만) 이고, 72 = 7 x 10 = 7 x (8 + 2) 로 표현이 가능하다.

 

이처럼 뺄셈으로 표현하기 위해서 divisor 와 2의 승수를 곱한 값을 dividend 에서 빼 나가는 방식으로 문제를 풀이했는데 c++ 에서 int 자료형의 표현 범위로 인한 오류가 발생해서 이는 따로 예외처리 하도록 했다.

 

위의 풀이로 작성한 코드는 다음과 같다.

 

class Solution {
public:
    int divide(int dividend, int divisor) {
        if (dividend == INT_MIN && divisor == -1)
            return INT_MAX;
        if (divisor == 1)
            return dividend;
        bool neg = (dividend >> 31) ^ (divisor >> 31);
        long dvd = abs(dividend), dvs = abs(divisor);
        int ans = 0;
        while (dvd >= dvs){
            long tmp = dvs, m = 1;
            while ((tmp << 1) <= dvd){
                tmp <<= 1;
                m <<= 1;
            }
            dvd -= tmp;
            ans += m;
        }
        return (neg ? -ans : ans);
    }
};