[LeetCode] Add Two Numbers - Javascript

Add Two Numbers

[두 개의 연결리스트의 합]

 

제약 조건 

The number of nodes in each linked list is in the range [1, 100].
0 <= Node.val <= 9
It is guaranteed that the list represents a number that does not have leading zeros.

 

Example

ex2) Input: l1 = [0], l2 = [0]
     Output: [0]

ex3) Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
     Output: [8,9,9,9,0,0,0,1]

 

초기 문제 접근 방식

처음엔 두 개의 연결리스트의 값에 접근해 값을 각각 arr1과 arr2 배열에 넣은 후 

각각의 배열을 정수로 변환해 더한 후 다시 배열로 만들어 리턴했다.

분명 example1) 과 같은 output을 제출 했는데도 1번 테스트 케이스가 풀리지 않아 고생을 좀 했다. 

이유를 문제를 다시 읽으며 알 수 있었다.

 "Add the two numbers and return the sum as a linked list."

값을 다시 연결리스트로 제출 했어야 했다. 

초기 전체코드

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function (l1, l2) {
   let sum = 0;

   arr = [];
   arr2 = [];
   arr3 = [];

   while (l1) {
      arr.push(l1.val);
      l1 = l1.next;
   }
   while (l2) {
      arr2.push(l2.val);
      l2 = l2.next;
   }
   arr = arr.reverse();
   arr2 = arr2.reverse();

   arr = arr.join('');
   arr2 = arr2.join('');

   sum = parseInt(arr) + parseInt(arr2);
   arr3 = (sum + '').split('');
   arr3.reverse();
   console.log(arr3);
   return arr3;
};

 

다시 생각 해보며..

우선 노드의 값을 더하는 방식을 변경했다.

기존과 같이 노드의 값을 배열에 넣은 후 정수로 바꿔 더하기를 하니

테스트케이스의 엄청 큰 수가 들어왔을때 해당 수가 2^53승을 넘어서 더하기가 안되는 경우가 발생했다.

그래서 아래와 같은 연산법을 사용했다.

 

예를들어. [2,4,3]과 [5,6,4]를 서로 더해 708이 나와야 한다면,

2+5 = 7

4+6 = 10

3+4 = 7 이지만 두번째 연산인 4+6에서 자리 올림이 발생했기에 두번째 자리 수는 0이되고 세번째 자리수는 8이 된다.

      sum = digit + (l1?.val ?? 0) + (l2?.val ?? 0);
      arr.push(sum % 10);
      digit = Math.floor(sum / 10);
      l1 = l1?.next;
      l2 = l2?.next;

이와 같은 예시를 일반화하자면
0에서 9까지의 숫자 중 2개를 더했을 때의 1의 자릿수를 구하려면 더한 값의 10을 나눈 나머지 값이 되고,
다음 연산은 더한 값의 10을 나눈 몫을 더해야 한다.

그 후 배열에 reverse를 하고
변수 ans를 생성해 obj의 주소를 저장해둔다.
반복문을 순회하며 ListNode 객체를 생성해 obj.next에 넣은 후
obj는 obj.next로 업데이트해준다.
이렇게 하면 obj는 그다음 next를 가리키게 되고
최종적인 리스트는 ans 변수가 주소를 가지고 있기에 해당 변수를 리턴하면 풀이가 된다.

주어진 클래스를 이용 해 node를 하나씩 생성한다

   let obj = {};
   let ans = obj;

   for (let i = arr.length; i >= 0; i--) {
      obj.next = new ListNode(arr[i]);
      obj = obj.next;
   }

 

solve 전체 코드

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */

var addTwoNumbers = function (l1, l2) {
   let sum = 0;
   const arr = [];
   let digit = 0;

   while (l1 || l2 || digit) {
      sum = digit + (l1?.val ?? 0) + (l2?.val ?? 0);
      arr.push(sum % 10);
      digit = Math.floor(sum / 10);
      l1 = l1?.next;
      l2 = l2?.next;
   }

   arr.reverse();

   let obj = {};
   let ans = obj;

   for (let i = arr.length; i >= 0; i--) {
      obj.next = new ListNode(arr[i]);
      obj = obj.next;
   }
   return ans.next.next;
};