알고리즘 문제 - 문자열 숫자 곱하기
2023. 4. 20.
시리즈 "알고리즘 문제풀기" 개요
- 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;
};
후기
어렵다기보다는 헷갈리는 문제였다. 하지만 침착하게만 하면 어떻게든 풀 수 있는 문제이기도 한 것 같다.