[Leetcode] 2. Add Two Numbers - JS

https://leetcode.com/problems/add-two-numbers/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

문제분석
--------------------
- 2개의 양의 정수를 나타내는 연결 리스트가 제공된다.
- 숫자는 역순으로 저장되며 각 노드에는 단일 숫자가 포함된다.
- 두 숫자를 더하여 그 합계를 연결 리스트로 반환하라.

제한조건
--------------------
- 연결리스트 속 node의 갯수는 1 ~ 100이다.
- 0 <= Node.val <= 9
- 리스트는 0을 향하지 않음을 보장한다.

 

2. 접근 방법

접근방법
--------------------
l1과 l2의 val 값을 더하여 새로운 node의 값으로 추가하면서 반복한다.

새로운 node를 dummyNode로 생성한다.
carry = 0 초기화, 자릿수 올림 저장하기 위한 변수

sum = l1Val + l2Val + carry 을 구한 뒤 이를 dummyNode에 추가한다.

carry 값은 올림 자릿수를 의미하니 Math.floor(sum / 10) 으로 갱신한다.

l1과 l2를 각각 따로 체크해서 l1.next, l2.next로 갱신한다.

 

 

3. 코드

var addTwoNumbers = function(l1, l2) {
    let dummyNode = new ListNode();
    let currentNode = dummyNode;
    let carry = 0;

    while (l1 || l2 || carry) {
        let l1Val = l1 !== null ? l1.val : 0;
        let l2Val = l2 !== null ? l2.val : 0;

        let sum = l1Val + l2Val + carry;

        carry = Math.floor(sum / 10);

        currentNode.next = new ListNode(sum % 10)

        currentNode = currentNode.next;

        if (l1) l1 = l1.next;
        if (l2) l2 = l2.next;
    }
    return dummyNode.next
};

 

while 반복문에 carry !== 0 일 때도 조건을 추가해준 이유는 올림 자릿수가 존재하면 해당 올림 자릿수를 Node로 추가해줘야한다.

 

4. 복잡도 분석

- 시간복잡도: O(n)

- 공간복잡도: O(n)

 

처음에는 l1과 l2의 값들을 문자열로 저장한 뒤, 숫자로 변환해서 합쳤다.

이 후 이를 dummyNode를 생성해서 값들을 하나씩 역순으로 추가해줬다.

 

하지만, 연결리스트 길이가 100까지 될 수있다. 즉, 자릿수가 100자리 까지 될 수 있는데 이 때 JavaScript의 Number() 메서드가 처리할 수 있는 숫자보다 크게 되는 경우가 발생하여 예상치 못한 오류가 발생하였다.

 

그래서 변경한 방법은 l1, l2의 각 자릿수를 더하면서 올림 변수를 저장하여 다음 자릿수 계산 시 올림 자릿수를 반영하여 새로운 리스트를 만들어 나가는 방법을 선택했다.

 

위 방법은 GPT를 통해서 공부했다.

 

자바스크립트의 Number가 처리할 수 없을 때, 어떻게 접근할 수 있는지 해결책을 하나 배울 수 있는 문제여서 재밌었다.