[Leetcode/TS] 2. Add Tow Number

문제

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

---

 

연결 리스트는 자료구조 면접 준비할 때 처음 개념 접한 것 외에는 아는 게 없어서 우선 얘를 보통 어떻게 구현하고 어떻게 사용하는지를 알아봤다.

 

문제에 사용되는 연결리스트 클래스

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
 
 
 
console.log({ l1 })       // [2, 4, 3]
console.log(l1.next)      // [4, 3]
console.log(l1.next.val)  // Error

 

 

연결리스트 하나를 콘솔에 찍었을 때 평범한 리스트처럼 나오길래 그럼 다음 노드도 바로 next.val 로 접근 가능하지 않을까 했는데 TypeError 로 null 값으로 접근 불가능했다. => 다음 노드가 없으면 당연히 안 나옴

==> null 이 아닌 한을 조건으로 

 

 

 

 

1.

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {

    const node1 = Number(convertedNode(l1).join(''));
    const node2 = Number(convertedNode(l2).join(''));

    const sumArray = String(node1 + node2).split('')
    console.log({ sumArray })
    
    // linked list 변환
    return sumArray.reduce((acc, sum) => {
        console.log({ acc })
        if (!acc) {
            acc = new ListNode(Number(sum))
        } else {
            acc = new ListNode(Number(sum), acc)
        }
        return acc;
    }, new ListNode()))
};

const convertedNode = (node: ListNode | null) => {
    const array = [node.val];

    while(node.next !== null) {
        node = node.next;
        array.push(node.val)
    }

    return [...array].reverse();
}

 

{ sumArray: [ '8', '0', '7' ] }
{ acc: ListNode { val: 0, next: null } }
{ acc: ListNode { val: 8, next: ListNode { val: 0, next: null } } }
{
  acc: ListNode { val: 0, next: ListNode { val: 8, next: [ListNode] } }
}

 

reduce 사용시 초기값을 new ListNode() 로 설정해놔서 제일 처음 val 이 0으로 들어가서 생긴 에러

 

 

    return sumArray.reduce((acc, sum) => {
        console.log({ acc })
        if (!acc) {
            acc = new ListNode(Number(sum))
        } else {
            acc = new ListNode(Number(sum), acc)
        }
        return acc;
    }, null as ListNode);

 

통과

된 줄 알았는데 아님

=> 한번에 덧셈 처리하려고 하면 이런 너무 큰 숫자로 인한 에러 나옴

 

 

 

 

 

 

 

 

2. 다른 사람 풀이

function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    const node = new ListNode(); // 빈 노드 생성 (헤드)
    let tmpNode = node; // node 를 참조 (원본)
    let carry = 0; // 덧셈에서 발생하는 올림값 저장용

    while (l1 || l2 || carry) {
        tmpNode.next = new ListNode();// next 에 새로운 객체 생성하여 연결

		tmpNode = tmpNode.next; // 새로 생성된 객체로 참조 방향 옮김

        const node1 = l1 ? l1.val : 0;
        const node2 = l2 ? l2.val : 0;
        let sum = node1 + node2 + carry;

        tmpNode.val = sum < 10 ? sum : sum % 10;
        carry = sum < 10 ? 0 : 1;

        l1 = l1 ? l1.next : null;
        l2 = l2 ? l2.next : null;
    }

    return node.next;
};

 

next:  ListNode { val: 0, next: null }
{ tmpNode: ListNode { val: 0, next: null } }
{ l1: [4,3], l2: [6,4] }
next:  ListNode { val: 0, next: null }
{ tmpNode: ListNode { val: 0, next: null } }
{ l1: [3], l2: [4] }
next:  ListNode { val: 0, next: null }
{ tmpNode: ListNode { val: 0, next: null } }
{ l1: null, l2: null }
{
  node: ListNode { val: 0, next: ListNode { val: 7, next: [ListNode] } }
}

 

제일 처음 노드의 val 부터 차례로 값을 구하고 새로운 더미 노드의 val 에 할당

참조 위치를 옮겨가며 val 과 next 에 다음값들을 할당

 

 

 

 

 

 

 

 

---

다시 풀었을 때 비슷하게라도 풀 수 있을지 전혀 모르겠다