[leetcode] 415. Add Strings

문제 : https://leetcode.com/problems/add-strings/

---

가산기 구현 문제.

학창시절에 배운적이 있는데 그때의 기억을 되살려서..

carry 변수를 하나 둔다. 올림되는 수가 있다면 1, 아니면 0일 것이다.

입력 문자열 num1, num2의 인덱스 변수를 ind1, ind2로 두고 해당 변수들은 입력문자열의 가장 뒤의 인덱스를 초기화 값으로 가진다. 덧셈뺄셈을 할 때, 같은 자리수에 있는 수들을 더해야 하기 때문이다.

num1[ind1], num2[ind2]를 각각 변수 a, b라 하자. 만일 ind1, ind2가 문자열 num1, num2의 인덱스 범위를 넘어선다면(0 미만) 0으로 본다. 탐색 후 ind1, ind2를 1씩 감소시킨다.

a + b + carry 를 나누기 10 했을 때의 나머지 값이 정답문자열의 가장 앞에 넣고, 몫을 carry에 넣는다.

ex) 7 + 6 = 13. 3을 정답에 넣고 1을 carry에 넣는다.

위와 같은 계산을 ind1, ind2 중 0이상인 값이 있거나 carry가 1이상인 값이 있는 경우 계속 반복한다.

 

ex) num1 = "456", num2 = "77"

ind1	ind2	a	b	carry	a + b + carry	정답 문자열
2	1	6	7	0	13	3
1	0	5	7	1	13	33
0	-1	4	0	1	5	533
-1	-1	0	0	0	종료	종료

 

시간복잡도는 num1, num2 문자열 길이 중 긴 길이가 N이라 할 때, O(N)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/415.%20Add%20Strings.cpp