Problem,
Given two non-negative integers, num1
and num2
represented as string, return the sum of num1
andnum2
as a string.
You must solve the problem without using any built-in library for handling large integers (such as BigInteger
). You must also not convert the inputs to integers directly.
Example 1:
Input: num1 = "11", num2 = "123"
Output: "134"
Example 2:
Input: num1 = "456", num2 = "77"
Output: "533"
Example 3:
Input: num1 = "0", num2 = "0"
Output: "0"
Solution,
๋์ด๋ ์ตํ์ ๋ฌธ์ ๋ก ๋ค์์ ํ๋์ฉ ๋ํด๊ฐ๋ฉด ๋์ด๋ค. ์ฐ์์ ์์ญ(..)
num1
์ ๋ง์ง๋ง ์์์num2
์ ๋ง์ง๋ง ์์๋ฅผ ๋ํ๋ค- ๋ ์งํฉ ๋ชจ๋ ๊ฐ์ ๋ฐฉ์์ผ๋ก ์ํํ๋ฉฐ ๋ํ๋ค
๋ํ ๋ 9๋ฅผ ์ด๊ณผํ๋ ์๊ฐ ๋์ฌ ์ ์๋ค. ์๋ฅผ ๋ค์ด ๋ณด์
num1 = "999"
num2 = "99999"
์ด๋ ๋ค๋ฉด,
9 + 9 = 18
1 + 9 + 9 = 19
1 + 9 + 9 = 19
...
๊ทธ๋ฌ๋ 10์ ๋๋ ๋๋จธ์ง๋ฅผ ๊ฐ์ผ๋ก ์ฐ๊ณ , ๋๋ ๊ฐ์ ์ฌ๋ฆฐ๋ค. ๋ญ ํธํ๋๋ก (..) ๊ฑ 1 ์ฌ๋ ค๋ ์๊ด ์๊ณ ์. carry = twoSum > 9 ? 1 : 0;
์ด๋๋ ๊ด์ฐฎ์๋ฐ ๋ญ.. ๋ด ์ทจํฅ์ ์๋๋ค.
class Solution {
public String addStrings(String num1, String num2) {
char[] alpha = num1.toCharArray();
char[] beta = num2.toCharArray();
var result = new StringBuilder();
int alphaSize = alpha.length - 1;
int betaSize = beta.length - 1;
int carry = 0;
for (;;) {
if (alphaSize < 0 && betaSize < 0) break;
int aResult = alphaSize >= 0 ? alpha[alphaSize] - '0' : 0;
int bResult = betaSize >= 0 ? beta[betaSize] - '0' : 0;
int twoSum = aResult + bResult + carry;
int val = twoSum % 10;
carry = val / 10;
result.append(val);
--alphaSize;
--betaSize;
}
if (carry != 0) result.append(carry);
return result.reverse().toString();
}
}
๊ทน๊ฐ์ ํจ์จ์ ์ํ๋ค๋ฉด Native array ๋ฅผ ์จ๋ ๊ด์ฐฎ์ ๊ฒ ๊ฐ๋ค. ๋ค๋ง ๋ฐฐ์ด ์ฌ์ด์ฆ ๋๋ฆฌ๋๊ฒ ๊ท์ฐฎ๋ค.
๊ณต๊ฐ ๋ณต์ก๋์ ๊ฒฝ์ฐ \(O(max(n, m))\) ์ด๊ธด ํ๋ค. ์๋ฆฌ๊ฐ ๋ฐ๋๋ ๊ฒฝ์ฐ๊ฐ ์๊ธฐ๋ 1์ ๋ํ๋ ๊ฒ๋ ๋ง๋ค. Big-O ํ๊ธฐ๋ฒ์ ์๋ง์ ๋ฟ.