문자배열을 이용한 큰 수 덧셈

• long long 형의 범위를 벗어난 수들을 + 연산자를 이용해 덧셈을 하게되면 오버플로우 발생
• 따라서 굉장히 큰 수에 대해서는 문자배열을 이용해 덧셈 진행

Algorithm

1. 문자 배열 (A, B) 2개를 뒤에서 부터 더해가며 새로운 문자 배열(result)에 저장
2. 1번 과정을 진행하면서 올림 수(sum)을 계속 저장
3. 문자 배열 A, B를 모두 순회하고 올림 수에 저장된 수가 없다면 result를 뒤집어 주고 종료

Ex. A = "12345", B = "666"

1. 5 + 6 = 11
   • 올림 수 1
   • result에 1 추가
   • sum = 1, result = "1"
2. 4 + 6 + sum = 11
   • 올림 수 1
   • result에 1 추가
   • sum = 1, result = "11"
3.  3 + 6 + sum = 10
   • 올림 수 1
   • result에 0 추가
   • sum = 1, result = "110"
4. 문자 배열 B 순회 종료. 따라서 2 + sum = 3
   • 올림 수 0
   • result에 3 추가
   • sum = 0, result = "1103"
5. 1 + sum = 1
   • sum = 0, result = "11031"
6. 문자 배열 A, B 순회 종료. 올림수 0. 따라서 result 뒤집어서 종료
   • result = "13011"

코드 구현

string string_add(string a, string b){
	int sum = 0;
    string result;
    while(!a.empty() || !b.empty() || sum){
    	if(!a.empty()){
        	sum += a.back() - '0';
            a.pop_back();
        }
        if(!b.empty()){
        	sum += b.back() - '0';
            b.pop_back();
        }
        result.push_back((sum%10) + '0');
        sum /= 10;
    }
    reverse(result.begin(), result.end());
    return result;
}