[4월 6일] Add Two Numbers

1. 문제 : Add Two Numbers

문제 설명

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

제한 사항

• 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.

풀이

/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */

function listNodeToArray(node) { // ListNode자료형 -> Array자료형 변환
  let result = [];
  let curr = node;
  while (curr !== null) {
    result.push(curr.val);
    curr = curr.next;
  }
  return result;
}
function arrayToListNode(arr) {  // Array자료형 -> ListNode자료형 변환
  let head = null;
  for (let i = arr.length - 1; i >= 0; i--) {
    const node = { val: arr[i], next: head };
    head = node;
  }
  return head;
}
var addTwoNumbers = function(l1, l2) {
    
    // const [list1,list2]=[[],[]]
    
    return arrayToListNode(((BigInt(listNodeToArray(l1).reverse().join('')) +  BigInt(listNodeToArray(l2).reverse().join('')))+'').split('').reverse().map(it=>+it))

};

• ListNode자료형을 다뤄야 하는 문제여서 ListNode > Array로 변환해주는 함수, Array > ListNode로 변환해주는 함수를 우선 만들어주었다.
• ListNode > Array로 변환하는 과정에서 노드가 길어서 number범위를 초과해 e를 이용한 식이 나오는 케이스가 있었다. 그래서 BigInt로 감싸서 범위를 초과해도 숫자로 표기되도록 하였다.
• ListNode > Array로 변환 후, reverse()를 이용해 순서를 역순으로 뒤집고, join('')으로 다시 합쳐주고, BigInt로 숫자로 변환해준 후, 더했다. 

다른 사람 풀이

var addTwoNumbers = function(l1, l2) {
    
    let sum = 0;
    let current = new ListNode(0);
    let result = current;
    
    while(l1 || l2) {
        
        if(l1) {
            sum += l1.val;
            l1 = l1.next;
        }
        
        if(l2) {
            sum += l2.val;
            l2 = l2.next;
        }
        
        current.next = new ListNode(sum % 10);
        current = current.next;
        
        sum = sum > 9 ? 1 : 0;
    }
    
    if(sum) {
        current.next = new ListNode(sum);
    }
    
    return result.next;
};

• Array <-> ListNode변환 안해서 풀 수도 있구나.
• l1과 l1를 val과 next를 이용해 순환하며 풀은 코드이다.

---

2. 느낀 점 / 배운 점

1. JS에는 ListNode라는 자료형이 있음. 오늘 처음 써봤다.

• 현재 노드 = listNode.val, 다음 노드 = listnode.next

function listNodeToArray(node) { // ListNode자료형 -> Array자료형 변환
  let result = [];
  let curr = node;
  while (curr !== null) {
    result.push(curr.val);
    curr = curr.next;
  }
  return result;
}

• Array > ListNode로 변환
  • Array를 뒤에서부터 순환
  • val에는 Array의 현재 순환 중인 값을, next에는 이전 노드의 값(head)을 넣음
  • head를 현재 노드로 교체해줌

function arrayToListNode(arr) {  // Array자료형 -> ListNode자료형 변환
  let head = null;
  for (let i = arr.length - 1; i >= 0; i--) {
    const node = { val: arr[i], next: head };
    head = node;
  }
  return head;
}

 

2. 큰 수를 다룰 때 e를 이용한 식이 나온다면, BigInt()로 전환해서 풀면 해결됨