[Programmers] #181846 - 두 수의 합 [Java][C++][Python]

문제 링크

---

1. 아이디어

두 정수가 문자열로 주어질 때 합을 구하는 문제로 두 수의 크기가 매우 크다. 큰 수의 연산을 지원하는 내장 기능을 활용하거나 직접 1의 자리부터 역순으로 합을 구하면 된다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N)$	$O(N)$

($N$ = a, b 중 더 긴 문자열의 길이)

---

3. 코드

풀이 [Java][C++][Python]

import java.math.*;

class Solution {
    public String solution(String a, String b) {
        BigInteger x = new BigInteger(a);
        BigInteger y = new BigInteger(b);
        return x.add(y).toString();
    }
}

BigInteger 클래스가 큰 정수 연산을 지원하므로 이를 활용해 두 수의 합을 간단하게 구했다.

#include <bits/stdc++.h>
using namespace std;

string solution(string a, string b) {
    string s;
    int i = a.size() - 1, j = b.size() - 1, carry = 0;
    while (i >= 0 || j >= 0 || carry) {
        int sum = carry;
        if (i >= 0) sum += a[i--] - '0';
        if (j >= 0) sum += b[j--] - '0';
        s += sum % 10 + '0';
        carry = sum / 10;
    }
    reverse(s.begin(), s.end());

    return s;
}

import sys

sys.set_int_max_str_digits(0)


def solution(a, b):
    return str(int(a) + int(b))

a, b의 길이가 최대 100,000이어서 Python으로도 바로 덧셈이 안 된다. sys.set_int_max_str_digits(0)로 먼저 정수 자릿수 제한을 풀어 놓고 덧셈을 진행했다.

---