[LeetCode][Java] Divide Two Integers

최지수·2021년 11월 29일

Algorithm

목록 보기

32/77

문제

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}$ .

제한사항

$-2^{31}$ <= dividend, divisor <= $2^{31} - 1$
divisor != 0

접근

곱셈, 나눗셈 그리고 나머지 연산을 이용하지 않고 나눗셈 연산을 구하는 문제였습니다. 문제를 보고 비트 연산을 응용하는 문제구나라는 것을 깨닫고 전개했습니다.

다만, 음수의 경우 비트 연산을 할 수 없기 때문에 양수로 바꿔주는 사전 작업을 진행하고 이후 dividend와 divisor의 음수 여부를 통해 예외 처리를 해줬습니다.

여기서 제일 큰 문제는 주어진 변수가 int형이라는 것이었고, 연산 과정에서 오버플로우overflow가 발생할 가능성이 존재한다는 것이었습니다. 그래서 저 같은 경우엔 int보다 더 큰 값을 저장할 수 있는 long 변수를 활용했고, 연산 결과가 int 범위를 벗어나게 되는 경우를 예외 처리하는 방식으로 전개했습니다.

답안

class Solution {
    public int divide(int dividend, int divisor) {
        long dividend2 = dividend;
        boolean isDividendMinus = dividend < 0;
        if(isDividendMinus)
            dividend2 = -dividend2;

        long divisor2 = divisor;
        boolean isDivisorMinus = divisor < 0;
        if(isDivisorMinus)
            divisor2 = -divisor2;

        long ret = 0;
        while(divisor2 <= dividend2){
            int mask;
            for(mask = 0; mask <= 30; ++mask){
                if((divisor2 << (mask + 1)) > dividend2)
                    break;
            }

            ret += (1L << mask);
            dividend2 -= (divisor2 << mask);
        }

        if((isDividendMinus && !isDivisorMinus) || (!isDividendMinus && isDivisorMinus)){
            if(-ret < Integer.MIN_VALUE)
                ret = (Integer.MIN_VALUE + 1);
            return (int)-ret;
        }
        
        if(ret > Integer.MAX_VALUE)
            ret = Integer.MAX_VALUE;
        
        return (int)ret;
    }

}