LeetCode: 29번 (Divide Two Integers) [JAVA]

문제 링크

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

Divide Two Integers - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 주어진 dividend와 divisor의 음수 여부를 파악하고, 음수라면 양수로 변환
2. 이후 while문으로 주어진 dividend에 다다를 때까지 시프트 연산 기반 근사값을 찾는 함수를 실행
   1) 주어진 숫자에 num에 대해 divisor 값을 기초로, 해당 값이 num보다 작을 때까지 해당 숫자를 시프트 연산
   2) 이후 해당 값을 acc에 누적하고, 따로 시프트 연산을 하며 얻은 몫 또한 답에 누적
3. 최종적으로 주어진 answer값에 앞선 dividend와 divisor의 음수 여부를 고려해 마이너스 여부를 확정
4. 이후 answer 값에 따라 적절한 값을 반환

 문제에서 주어진 dividend와 divisor을 바탕으로 나눈 몫을 반환하는 문제인데, 조건은 곱셈과 나누기, 그리고 mod 연산을 사용하면 안된다. 그러기 때문에 초기에는 단순히 반복문을 기반으로 divisor을 무한히 더하는 방법으로 dividend에 근사한 몫을 구하려 했지만, 이런 경우엔 시간 초과가 발생하게 된다.
 이에 떠올린 대안으로는 시프트 연산을 활용하여 빠르게 dividend에 근사한 divisor의 배수를 찾는 방법을 사용했다. 다만 단순히 시프트 연산으로 divisor의 배수를 찾는 경우 몫이 2의 제곱수로만 될 뿐 완전한 정답이 되지 않기 때문에, 이를 반복하여 이전 결과값 만큼을 기존 dividend에 빼고 그 남은 값에 대해 다시 한 번 근사값을 찾는 과정을 반복하는 것으로 했다. 그렇게 얻은 답을 최종적으로 dividend와 divisor의 음수 여부를 바탕으로 마이너스를 붙일 지를 결정하고, 그 값에 따라 적절한 값을 반환하도록 했다.

 

class Solution {
    long acc = 0, answer = 0;
    boolean closeToDividend = false;

    public int divide(int dividend, int divisor) {
        boolean isDividendMinus = false, isDivisorMinus = false;
        long dividendTemp = dividend, divisorTemp = divisor;

        if (dividend < 0) {//dividend 음수 여부
            isDividendMinus = true;
            dividendTemp = -dividendTemp;
        }

        if (divisor < 0) {//divisor 음수 여부
            isDivisorMinus = true;
            divisorTemp = -divisorTemp;
        }

        while (!closeToDividend) {//dividend에 다다를 때까지
            shiftCal(dividendTemp - acc, divisorTemp);
        }

        if (isDividendMinus ^ isDivisorMinus) {//결과에 마이너스 추가 여부
            answer = -answer;
        }

        if (answer >= Integer.MAX_VALUE) {
            return Integer.MAX_VALUE;
        } else if (answer <= Integer.MIN_VALUE) {
            return Integer.MIN_VALUE;
        } else {
            return (int) answer;
        }
    }

    void shiftCal(long num, long divisor) {//시프트 연산 기반 나누기
        if (num < divisor) {
            closeToDividend = true;
            return;
        }

        long quotient = 1, temp = divisor;

        do {
            temp = temp << 1;
            quotient = quotient << 1;
        } while (temp <= num);
        temp = temp >> 1;
        quotient = quotient >> 1;

        acc += temp;
        answer += quotient;
    }
}

결과