[알고리즘/자바스크립트] 덧셈 알고리즘 (Adding Big Numbers)

-해당 문제는 codewars사이트의 level4 문제입니다. (1~8단계 중 8단계가 가장 쉬운 레벨)-

[문제] We need to sum big numbers and we require your help.

Write a function that returns the sum of two numbers. The input numbers are strings and the function must return a string.

- Example

add("123", "321"); -> "444"

add("11", "99"); -> "110"

- Notes

The input numbers are big.

The input is a string of only digits

The numbers are positives

[해석] 매우 큰 숫자들을 더하는 함수를 만들어라. 주어지는 숫자들은 모두 string 형태로 주어질 것이고 return하는 숫자도 string 형태여야 한다.

중요한건 주어지는 숫자가 매우 매우 큰 숫자라는 것이다. (양수만 주어질 것임)

처음에 이 문제를 봤을 때는 그냥 문자열로 주어진 숫자를 Number 타입으로 바꾸고 더해서 

다시 string 타입으로 바꾸면 되는 것이 아닌가(?) 하는 생각을 했다.

그게 뭐 별거라고(?)

이게 왜 4레벨 문제야(?)

근데 당연하게도 이 문제는 그런 쉬운 문제가 아니었다...

처음 이 문제의 답을 적는 곳에는 이렇게 적혀있었다.

function add(a, b) {
	return (Number(a) + Number(b)).toString()	// fix me!
}

그리고 아래와 같은 어마어마하게 큰 숫자로 이루어진 테스트 데이터가 있는데

add('63829983432984289347293874', '90938498237058927340892374089')

이대로 테스트를 돌려보면 에러가 뜨면서 다음과 같은 결과창이 나온다.

"91002328220491911630239667963"가 답인데 "9.100232822049192e+28"이 출력된다고.

그렇다.. 자바스크립트는 어느 정도 길이의 숫자까지는 그냥 쭉 표기하지만

특정 자리수를 넘기는 큰 숫자는 e+를 사용해서 표현하고 있다.

console.log(Number('100000000000000000000'))  // 100000000000000000000
console.log(Number('1000000000000000000000')) // 1e+21

위 결과를 보면 100,000,000,000,000,000,000 까지는 그냥 숫자가 바로 출력되지만

0을 하나 더 붙인 1,000,000,000,000,000,000,000는 1e+21이라고 표기된다. 

(e+21은 10의 21승을 말하고 1e+21은 1과 10의 21승을 곱한 값을 의미한다.

인터넷을 찾아보니 이런 표기법을 "지수 표기"라고 한다.)

하여튼 ... 그래서 저 큰 숫자들을 더하면서도 지수 표기법을 피해가려면 다른 방법을 통해서 더해야된다는 결론이 나온다.

그래서 인터넷 검색도 좀 해보고 고민도 해 본 끝에

생각해낸 해결 방법은 다음과 같다.

우리가 잘 알고 있는 덧셈의 매커니즘을 자바스크립트로 표현해보는 것이다.

function add(a, b) {
	var result = []

	var lenDif = a.length - b.length
	if(lenDif < 0) {
		a = a.padStart(b.length, '0')
	} else if(lenDif > 0) {
		b = b.padStart(a.length, '0')
	}

	var move = 0;
	for(var i=a.length; i>0; i--) {
		var sum = Number(a.slice(i-1, i)) + Number(b.slice(i-1, i)) + move
		if(sum >= 10) {
			if(i !== 1) {
				move = 1
				sum = sum.toString().slice(1)
			} else {
				sum = sum.toString()
			}
		} else {
			move = 0
			sum = sum.toString()
		}
		result.splice(0, 0, sum)
	}
	return result.join('')
}

3219라는 숫자와 123이라는 숫자를 더한다고 했을 때

1. 먼저 두 숫자의 자리수를 맞춰주기 위해서 숫자 길이를 비교한다.
   
2. 3219는 4자리수, 123은 3자리수이므로 3자리수인 123맨 앞에 0을 추가하여 둘 다 4자리수로 맞춰준다.
3. 반복을 돌면서 뒤에서부터 각각의 자리수를 더해준다.
4. 그 더한 값이 10보다 크거나 같으면 더한값의 마지막 1자리수만 남기고 앞의 숫자 1은 move라는 변수에 담는다. 마지막 한자리 수는 result라는 배열에 넣는데 splice(0, 0, sum)으로 배열의 맨 앞자리에 넣는다.
5. 다음 자리수 더할 때 move에 담긴 수와 함께 더하여 result배열 맨 앞에 넣고 만약 그 값이 10보다 작으면 move는 0으로 초기화시켜준다.
6. 뒤에서부터 차근차근 더한 후 마지막 덧셈을 할 때는 더한 값이 10보다 크거나 같더라도 쪼개지 않고 그대로 result 배열 맨 앞에 넣는다.
7. result의 모든 요소를 join('')으로 string으로 만들어서 출력한다.

끝!!