시리즈 "알고리즘 문제풀기" 개요

  • 1~2주 (최소) 1개 문제 풀기를 목표로 한다.
  • JavaScript 로 푼다.

문제

LeetCode - 43. Multiply Strings

문자열로 표현된 두 개의 숫자를 num1, num2 를 곱해서 결과를 반환하자.

숫자는 최소 1자리에서 최대 200자리까지 가능하다. BigInt 같은 내장 라이브러리는 쓰면 안 된다.

접근

실제로 곱셈을 할 때와 동일하게 생각해보았다. 보통 세 자리 수 두 개를 곱한다고 하면 아래처럼 계산한다.

  123
x 456
-----
  738
 615
492
-----
56088

한 숫자에 자랏수마다 다른 한 숫자를 곱한 뒤 곱한 결과를 합하는 것이다. 이걸 코드로 그대로 구현하면 되겠다 싶었다.

풀이 1

var multiply = function (num1, num2) {
  // 둘 중 하나라도 "0" 이라면 바로 결과를 반환한다.
  if (num1 === "0") return "0";
  if (num2 === "0") return "0";

  // 곱셈을 편하게 하기 위해 두 숫자를 배열로 만든뒤 뒤집는다.
  // 뒤집는 건 사실 필수가 아니지만, 인덱스를 좀 더 편하게 생각하려고 뒤집었다.
  const a1 = num1.split("").reverse();
  const a2 = num2.split("").reverse();

  let result = ["0"];
  for (let j = 0; j < a2.length; j++) {
    // (`num1` * `num2` 의 j 번째 숫자) 의 결과를 얻는다.
    // `getMultiplyWithOneDigit` 함수의 코드는 26 라인에 나온다.
    const subResult = getMultiplyWithOneDigit(a1, a2[j], j);
    // 결과값에 `subResult` 값을 합산한다.
    // `addTo` 함수의 코드는 59 라인에 나온다.
    addTo(result, subResult);
  }

  // 결과를 반환한다.
  return result.reverse().join("");
};

// a1 과 n 을 곱한다. (digit 는 n 이 a2 의 몇 번째 자릿수였는지 알려주는 값.)
var getMultiplyWithOneDigit = function (a1, n, digit) {
  // 곱하려는 값이 "0" 이면 "0" 을 바로 반환한다.
  if (n === "0") {
    return ["0"];
  }

  // `n` 의 자릿수만큼 "0"으로 채운다.
  // 예를 들어 `a1` 이 "123" 이고 `n` 이 "456" 중에 "4" 였다고 하면
  // 두 수의 곱의 결과는 "492" 지만, `n` 이 백의 자리 숫자였으므로
  // 결과에 합산하기 편하게 "49200" 으로 만들어준 것.
  const result = new Array(digit).fill("0");

  // `a1` 의 자릿수 별로 `n` 을 곱한다.
  // 곱한 결과가 10 이상이면 (결과 % 10) 만 저장하고
  // (결과 / 10) 은 다음 자릿수로 넘긴다.
  let more = 0;
  for (let i = 0; i < a1.length; i++) {
    const multiplied = +a1[i] * +n + more;
    const subResult = multiplied % 10;
    result.push(`${subResult}`);
    more = Math.floor(multiplied / 10);
  }

  // 다 곱했는데도 `more` 에 값이 있다는 것은 최종 자릿수의 곱셈 결과가
  // 10 이상이었다는 뜻이다. 그렇다면 해당 값도 밀어넣어주자.
  if (more > 0) {
    result.push(`${more}`);
  }

  return result;
};

// `result` 와 `adding` 을 더한다.
var addTo = function (result, adding) {
  // 더하려는 값 `adding` 이 "0" 이면 더해봤자 결과가 같으므로 바로 종료한다.
  if (adding.length === 1 && adding[0] === "0") {
    return;
  }

  let i = 0;
  let more = 0;

  // `result` 와 `adding" 을 자릿수별로 차례차례 더해서
  // 다시 `result` 에 넣는다.
  while (i < result.length || i < adding.length) {
    const added = +(result[i] ?? "0") + +(adding[i] ?? "0") + more;

    // (더한 결과 % 10) 만 현재 자릿수 값에 반영하고
    // (더한 결과 / 10) 은 다음 자릿수에 넘긴다.
    result[i] = `${added % 10}`;
    more = Math.floor(added / 10);

    i += 1;
  }

  // 덧셈을 다 끝냈는데 `more` 에 값이 남았다면 해당 값은 맨 앞자리에 붙여준다.
  if (more > 0) {
    result.push(`${more}`);
  }

  // `result` 에 결과를 바로 반영했으므로 값을 따로 반환할 필요는 없다.
};

개선점

위 코드도 문제 없이 동작한다. 하지만 개선점이 존재한다.

첫째로 숫자를 뒤집을 필요가 없다. 이건 순전히 생각하기 편하려고 뒤집었던 것이었고, 뒤집지 않아도 곱하는 데 문제가 없다.

둘째로 현재는 숫자를 자릿수 별로 곱한 뒤에, 곱한 값을 결과에 합산하고 있는데 이렇게 할 필요가 없다. 곱하면서 바로바로 결과에 합산해도 되기 때문이다. 이러면 코드가 더 단순해지고 불필요한 반복문도 제거할 수 있다.

그럼 이제 개선해보자.

풀이 2

var multiply = function (num1, num2) {
  if (num1 === "0") return "0";
  if (num2 === "0") return "0";

  // - num1 * num2 의 결과값의 길이는
  //   최소 num1.length + num2.length - 1
  //   최대 num1.length + num2.length
  // - 최대 길이만큼 결과 배열을 미리 만들어서 0으로 채워두었다.
  const resArr = new Array(num1.length + num2.length).fill(0);

  for (let i = num1.length - 1; i >= 0; i--) {
    for (let j = num2.length - 1; j >= 0; j--) {
      // i 번째 숫자와 j 번째 숫자를 곱한 값은 결과값의 i + j + 1 번째에 반영된다.
      const curr = i + j + 1;

      // 두 숫자를 곱한 뒤 현재 결과 자릿수의 값과 합산한다.
      const multiplied = resArr[curr] + +num1[i] * +num2[j];
      // 값이 10 이상이면 10을 나눈 나머지만 해당 자릿수에 반영한다.
      resArr[curr] = multiplied % 10;
      // 값을 10으로 나눈 값을 바로 윗자릿수에 합산한다.
      resArr[curr - 1] += Math.floor(multiplied / 10);
    }
  }

  // 결과 배열을 문자열로 만든다.
  const result = resArr.join("");

  // - 만약 첫 자릿수의 값이 0이라면 쓸모 없는 값이므로 해당 값을 잘라낸다.
  // - 왜 첫 자릿수의 값이 0인 경우가 생기냐면
  //   최대 자릿수 num1.length + num2.length 만큼 미리 0을 채워놨기 때문이다.
  //   결과가 최소 자릿수 num1.length + num2.length - 1 일 경우 첫 번째 자릿수는 0으로 남게 된다.
  return result[0] === "0" ? result.slice(1) : result;
};

후기

어렵다기보다는 헷갈리는 문제였다. 하지만 침착하게만 하면 어떻게든 풀 수 있는 문제이기도 한 것 같다.