ReetCode 2.Add Two Numbers

초기 접근

처음 문제를 풀려했을때는 리스트에 값을 저장한뒤 reverse()메소드를 통해 뒤집고 join('')하여 parseInt()를 통해 정수로 만들고 더한 뒤 다시 이를 배열로 만들어 링크드 리스트에 저장하는 방식으로 접근했다.
하지만 수의 크기가 너무 커졌을때 문제가 해결되지 않는 경우가 발생 했다.

해결책

그래서 생각해 낸 해결책이

/**
 * 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 str1 = [];
    let str2 = [];
    while(l1) {
        str1.push(l1.val);
        l1 = l1.next;
    }
    while(l2) {
        str2.push(l2.val);
        l2 = l2.next;
    }
    let sum = [];
    let up = 0;
    while (str1.length || str2.length) {
        if (!str1.length) {
            let cur = str2.shift() + up;
            if (cur > 9) {
                cur = cur % 10;
                up = 1;
            } else {
                up = 0;
            }
            sum.push(cur);
            console.log(cur);
        } else if (!str2.length) {
            let cur = str1.shift() + up;
            if (cur > 9) {
                cur = cur % 10;
                up = 1;
            } else {
                up = 0;
            }
            sum.push(cur);
            console.log(cur);
        } else {
            let cur = str1.shift() + str2.shift() + up;
            if (cur > 9) {
                cur = cur % 10;
                up = 1;
            } else {
                up = 0;
            }
            sum.push(cur);
            console.log(cur);
        }
    }
    if (up == 1) {
        sum.push(up);
    }
    sum.reverse();
    let newNode = new ListNode();
    const res = new ListNode();
    res.next = newNode
    let length = sum.length
    for (let i = 0; i < length; i++) {
        newNode.next = new ListNode(parseInt(sum.pop()));
        newNode = newNode.next;
    }
    return res.next.next;
};

이처럼 문자열을 그대로 하나하나씩 더해 주는 방법이다.
문제는 해결했지만 너무 난잡하고 보기에 어렵다.
해서 다른 solution을 참고하여 내 코드와 비교해보자.

다른 방법

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    var List = new ListNode(0);
    var head = List;
    var sum = 0;
    var carry = 0;
    while(l1!==null||l2!==null||sum>0){
        if(l1!==null){
            sum = sum + l1.val;
            l1 = l1.next;
        }
        if(l2!==null){
            sum = sum + l2.val;
            l2 = l2.next;
        }
        if(sum>=10){
            carry = 1;
            sum = sum - 10;
        }
        head.next = new ListNode(sum);
        head = head.next;
        sum = carry;
        carry = 0;
    }
    return List.next;
};

아주 유사해보이지만 다르다.... 나는 리스트에 담고 문자열에 담아 메모리 낭비를 심하게 했으나 이 코드는 더하는 방식은 비슷하지만 그 값을 바로 링크드 리스트로 연결시킴으로서 가독성도 공간복잡도도 모두 보다 나은 코드로 보인다.

결론

너무 복잡하게 생각해서 문제를 해결하려다 보니 발생한 문제가 아닌가 싶다.
좀 더 유연하고 개방적인 사고를 할 수 있도록 노력해야겠다.

솔루션 출처(references) : https://leetcode.com/problems/add-two-numbers/solutions/1020/javascript-solution/?orderBy=most_votes&languageTags=javascript