Add Two Numbers

December 21, 2024

문제 링크

해결 방법 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 l1Length = getLength(l1);
  const l2Length = getLength(l2);

  let l1ToRevStr = "";
  for (let i = l1Length - 1; i >= 0; --i) {
    l1ToRevStr = l1.val + l1ToRevStr;
    l1 = l1.next;
  }

  let l2ToRevStr = "";
  for (let i = l2Length - 1; i >= 0; --i) {
    l2ToRevStr = l2.val + l2ToRevStr;
    l2 = l2.next;
  }

  let sumRevLists = BigInt(l1ToRevStr) + BigInt(l2ToRevStr);
  let revSumRevLists = sumRevLists.toString().split("").reverse().join("");

  let head = new ListNode(Number(revSumRevLists[0]));
  let tail = head;

  for (let i = 1; i < revSumRevLists.length; ++i) {
    tail.next = new ListNode(Number(revSumRevLists[i]));
    tail = tail.next;
  }

  return head;

  function getLength(head: ListNode | null): number {
    let count = 0;
    let current = head;

    while (current) {
      count++;
      current = current.next;
    }

    return count;
  }
}

연결리스트 문제다. 먼저, 인자로 들어오는 두 연결리스트의 길이를 구해주는 함수를 만들었다. 이 함수로 구한 길이를 이용해 반복문을 돈다. 그 안에서 연결리스트의 연결된 값들을 문자열로 이어 붙인 후 뒤집는다. 그 다음 두 문자열을 숫자로 변환해 더한 뒤 문자열로 다시 변환해 뒤집는다. 그리고 그 값을 연결리스트로 만들어 결과 값으로 반환한다. 이를 위해 연결리스트의 head를 먼저 만들고 그 뒤로 연결해 나갈 tail을 만들어 뒤를 이어준 뒤 최종 값을 반환했다. 문자열로 변환하고 뒤집고 하는 과정을 거치지 않고 더 간단하게 풀 수 있었으면 했다. 하지만 마땅히 방법이 떠오르지 않았다. 아쉬운 부분이었다.

연결리스트 자료구조의 개념과 활용 방법을 이번 문제를 풀면서 알게 되었다. 처음에는 head와 tail을 사용하는 이유와 방법에 대해서 몰랐다. 그래서 tail 없이 head만 사용했다(처음에는 변수 이름 head 아니었음. 될 줄 알았음...). 그랬더니 새로 추가한 노드가 계속해서 이전 노드를 덮어쓰다가 마지막에 덮어쓴 노드만 반환되는 결과가 나왔다. 왜 그런가 곱씹어봤다. 뭔가 메모리(스택 힙), 참조, 가비지 컬렉터와 연관이 있는 것 같았다. 아니나 다를까 잘 생각해보니 head가 따로 가장 윗대가리(?) 노드를 참조하고 있지 않으면 참조 연결이 유지되지 않는 게 당연했다. 노드를 일단 한 번 만들어 놓으면 없어지지 않을 거라 착각했다. 결론은 head의 노드 참조가 유지되어야 tail이 노드 연결을 이어나갈 수 있다. 참조가 끊어져 쓸모 없어진 메모리는 나중에 가비지 컬렉터가 줍줍하러 오겠지.

해결 방법 2

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode tail = dummyHead;
        int carry = 0;

        while (l1 != null || l2 != null || carry != 0) {
            int digit1 = (l1 != null) ? l1.val : 0;
            int digit2 = (l2 != null) ? l2.val : 0;

            int sum = digit1 + digit2 + carry;
            int digit = sum % 10;
            carry = sum / 10;

            ListNode newNode = new ListNode(digit);
            tail.next = newNode;
            tail = tail.next;

            l1 = (l1 != null) ? l1.next : null;
            l2 = (l2 != null) ? l2.next : null;
        }

        ListNode result = dummyHead.next;
        dummyHead.next = null;
        return result;
    }
}

다른 분이 푸신 코드다. while문 하나만 사용했다. 내 방식보다 시간복잡도가 낮을 거라 예상했다. 실제로 돌려보니 더 빠른 결과가 나온다. 아마 공간복잡도도 내 방식보다 더 좋을 거라 예상한다. 몫, 나머지 연산자와 자리 올림(carry) 변수를 사용했다. 이런식으로도 활용할 수 있구나... 간결하고 효율적이며 창의적인 방식이다.

Search

Search Form

Results

Add Two Numbers