[LeetCode] Top Interview Problems 2. Add Two Numbers

🔗 문제 링크

https://leetcode.com/problems/add-two-numbers/

Add Two Numbers - LeetCode

✏️ 풀이

var addTwoNumbers = function(l1, l2) {
    const getNumber = (listNode) => {
        let node = listNode;
        let num = '';
        while (node) {
            num += node.val;
            node = node.next;
        }
        return BigInt([...num].reverse().join(''));
    };

    const getListNode = (num) => {
        const numStr = num.toString();
        const listNode = new ListNode(numStr[numStr.length - 1]);
        let lastNode = listNode;
        for (let i = numStr.length - 2; i >= 0; i--) {
            const node = new ListNode(numStr[i]);
            lastNode.next = node;
            lastNode = node;
        }
        return listNode;
    };

    return getListNode(getNumber(l1) + getNumber(l2));
};

getNumber로 연결리스트의 val을 모두 이어붙여 거꾸로 만든 수를 구하여 실제 덧셈을 한 후, 덧셈의 결과를 거꾸로 새로운 연결리스트로 만들었다. 그런데 연결리스트 길이가 길면 number 타입의 최댓값을 넘어가는 수가 나올 수 있기 때문에 BigInt를 사용해서 연산하였다.

 

그러나 아무리봐도 이 풀이는 문제를 낸 의도와는 맞지 않는 것 같았다.

 

var addTwoNumbers = function(l1, l2) {
    const getListNodeOfSum = (l1, l2) => {
        const newNode = new ListNode();
        let node1 = l1;
        let node2 = l2;
        let plus = false;
        let lastNode = newNode;
        while (node1 || node2) {
            const val1 = node1 ? node1.val : 0;
            const val2 = node2 ? node2.val : 0;
            const sum = val1 + val2;
            lastNode.val += (sum + plus < 10 ? sum : sum - 10) + plus;
            plus = sum + plus >= 10;
            node1 = node1 ? node1.next : node1;
            node2 = node2 ? node2.next : node2;
            if (node1 || node2) {
                lastNode.next = new ListNode();
                lastNode = lastNode.next;
            }
        }
        if (plus) {
            lastNode.next = new ListNode(1);
        }
        return newNode;
    };

    return getListNodeOfSum(l1, l2);
};

발상을 바꿔서 직접 숫자를 더하지 않고, 연결리스트를 타고 들어갈 때 두 연결리스트의 동일한 순서에 있는 노드의 val을 더하고 그 값으로 새로운 연결리스트에 저장하도록 하였다. 만약 더한 값이 10이 넘으면 덧셈에서의 받아올림을 위해 현재 노드는 두 노드의 val을 더한 값에서 10을 뺀 값을 갖고, 다음 노드는 두 노드의 val의 합에 1을 더 더한 값을 갖게 된다.

 

그런데 l1과 l2의 길이가 다를 수 있으므로, 두 연결리스트 마지막 노드를 탐색할때까지 이 과정을 반복한다. 그리고 만약 가장 마지막 노드에서 val이 10 이상이라면 마지막에 val로 1을 갖는 새로운 노드를 한 번 더 추가한다.

 

var addTwoNumbers = function(l1, l2) {
    const getListNodeOfSum = (l1, l2) => {
        const newNode = new ListNode();
        let carry = 0;
        let lastNode = newNode;
        while (l1 || l2 || carry) {
            const val1 = l1 ? l1.val : 0;
            const val2 = l2 ? l2.val : 0;
            const sum = val1 + val2 + carry;
            carry = Math.floor(sum / 10);
            const node = new ListNode(sum < 10 ? sum : sum - 10);
            lastNode.next = node;
            lastNode = node;
            l1 = l1 ? l1.next : l1;
            l2 = l2 ? l2.next : l2;
        }
        return newNode.next;
    };

    return getListNodeOfSum(l1, l2);
};

모범 답안을 보고 다시 위 코드를 깔끔하게 정리하였다.