문제 설명

입력으로 들어온 dividend를 divisor로 나누고 소수점을 제외한 결과를 출력한다. 단, 곱셈, 나눗셈, 나머지 연산을 사용해서는 안된다. 입력값의 범위는 C에서 int값의 범위와 같으며 (-2147483648 ~ 2147483647) 결과값도 같은 범위로 제한해야 한다.

풀이

간단한 문제처럼 보이지만 곱셈, 나눗셈, 나머지 연산을 사용해서는 안된다는 제약사항이 있다.

1. 첫 시도

나눗셈의 정의는 다음과 같다.

피제수 = 제수 x 몫

여기에서 제수 x 몫 부분을 풀어 쓰면 제수를 몫만큼 반복해서 더한 것과 같기 때문에, 나눗셈도 마찬가지로 제수를 몫만큼 반복해서 빼는 것으로 바꿔서 생각할 수 있다.
따라서 이 문제를 나눗셈 연산자 없이 루프를 돌면서 dividend가 divisor보다 작아지기 전까지 반복해서 빼고 그 횟수를 리턴하는 식으로 간단하게 구현해볼 수 있다.

/**
 * @param {number} dividend
 * @param {number} divisor
 * @return {number}
 */
var divide = function(dividend, divisor) {
    let result = 0;
    while (dividend >= divisor) {
        dividend -= divisor;
        result++;        
    }
    return result;
}

(* 부호 처리, 최대값 처리 같은 예외 처리가 빠져 있다)

하지만 dividend = 2147483647, divisor = 1 같은 극단적인 케이스를 만날 경우 루프를 dividend 횟수만큼 반복해야 하므로 시간 제한에 걸리게 된다. 개선이 필요하다.

2. 개선

1번을 개선하려면 루프를 도는 횟수를 줄여야 하고, 그러려면 dividend를 보다 빠르게 줄여 나가야 한다. 1번의 접근 방법에서 divisor 대신 divisor의 배수를 dividend에서 빼는 방법을 생각해볼 수 있다(단, 곱셈을 사용할 수 없으므로 divisor를 증가시킬 때 덧셈을 사용해야 한다).

1. dividend 보다 divisor가 작으면 divisor를 증가시킨다
2. dividend 보다 divisor가 크면 divisor를 감소시킨다
3. dividend가 초기 divisor보다 작아질 때까지 반복한다

이 방법으로도 성능을 크게 개선시킬 수 있지만, 구현이 다소 까다로웠다. 보다 간단한 알고리즘을 생각해보았다.

1. dividend 보다 작거나 같으면서 가장 큰 divisor를 찾는다
2. dividend가 초기 divisor보다 작아질 때까지 divisor를 줄여가면서 반복한다

divisor값을 줄여갈 때 나눗셈을 사용할 수 없기 때문에 계산하기가 애매한데, 루프를 돌면서 배열에 미리 divisor의 배수값을 저장한 다음 배열을 순회하는 방법을 사용했다. 최대한 큰 divisor값을 얻기 위해서 divisor값을 누적해서 더했고, 이 과정에서 몫도 미리 계산해서 저장했다.

ex) dividend = 22, divisor = 3일 경우

divisorStack = [3, 6, 12] // divisor의 모음
stepStack = [1, 2, 4] // 더해줄 몫의 모음
(divisorStack[k] = stepStack[k] * divisor)

가장 큰 divisor를 divisorStack에서 찾아서 divisorStack[k]라고 할 때, stepStack[k]의 값을 result에 더한다.

1) divisorStack[k] = 12
stepStack[k] = 4
divdend = 22 - 12 = 10
result = 4

2) divisorStack[k] = 6
stepStack[k] = 2
dividend = 10 - 6 = 4
result = 4 + 2 = 6

3) divisorStack[k] = 3
stepStack[k] = 1
dividend = 4 - 3 = 1
result = 6 + 1 = 7

남은 dividend보다 작거나 같은 divisor가 없으므로 루프를 종료하고 답은 result = 7이 된다.

3. 예외 처리

• dividend나 divisor가 음수로 들어올 경우 처리가 복잡해진다. dividend와 divisor를 일단 양수로 만들어서 계산하고, 최종 결과값의 부호를 변경하는 방법으로 처리했다.
• dividend와 divisor 모두 int 범위 내로 들어오기 때문에 대부분의 케이스에서는 결과값의 범위를 신경쓰지 않아도 된다. 하지만 dividend = -2147483648, divisor = -1처럼 결과값이 int 범위를 넘어가는 케이스가 있기 때문에 결과값을 int 범위 내로 제한해줘야 한다.

소스 코드

/**
 * @param {number} dividend
 * @param {number} divisor
 * @return {number}
 */
var divide = function(dividend, divisor) {
    let result = 0;
    const hasDifferentSign = dividend > 0 && divisor < 0 || dividend < 0 && divisor > 0;
    if (dividend < 0) {
        dividend = -dividend;
    }
    if (divisor < 0) {
        divisor = -divisor;
    }

    let divisorStack = [];
    let stepStack = [];
    let currentDivisor = divisor;
    let currentStep = 1;
    do {
        divisorStack.push(currentDivisor);
        stepStack.push(currentStep);
        currentDivisor += currentDivisor;
        currentStep += currentStep;
    } while (currentDivisor < dividend);
    
    let index = divisorStack.length - 1;
    while (dividend >= divisor) {
        while (index >= 0 && dividend < divisorStack[index]) {
            index--;
        }
        dividend -= divisorStack[index];
        result += stepStack[index];
    }
    result = hasDifferentSign ? -result : result;
    if (result > 2147483647) {
        result = 2147483647;
    }
    return result;
};