새싹프로그래머의 이야기

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

문제: 수를 역순으로 구성한 두 개의 linked-list가 존재할 때, 각 linked-list의 자리 수를 더한 결과 값을 구하는 문제

문제 설명:

문제에서 주어진 예시를 보면 다음과 같습니다.

342 는  2 -> 4 -> 3 으로 구성되며, 465는 5 -> 6 -> 4로 구성됩니다.

각 자리 수의 합을 구하면 807로 7 -> 0 -> 8로 구성된 linked-list를 반환하면 됩니다.

문제 코드:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        number1 = 0
        ten1 = 1
        number2 = 0
        ten2 = 1

        while True:
            number1 += (l1.val * ten1)
            if l1.next == None:
                break
            l1 = l1.next
            ten1 *= 10
        while True:
            number2 += (l2.val * ten2)
            if l2.next == None:
                break
            l2 = l2.next
            ten2 *= 10

        linked_list = None

        for i in list(str(number1 + number2)):
            cur = ListNode()
            cur.val, cur.next = i, linked_list
            linked_list = cur
        return linked_list

저 같은 경우, 각 linked-list의 값을 10진수로 변환한 후 더한 값을 구해 다시 liked-list를 구성하는 방식을 사용했습니다.

다른 풀이 코드를 보다 linked-list 자체로 풀이를 진행한 깔끔한 코드가 있어 소개해보고자 합니다.

그 코드는 다음과 같습니다.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        val = 0
        head = ListNode()
        linked_list = head
        while l1 or l2 or val:

            if l1:
                val += l1.val
                l1 = l1.next
            if l2:
                val += l2.val
                l2 = l2.next

            linked_list.next = ListNode(val % 10)
            linked_list = linked_list.next
            val //= 10

        return head.next

linked-list에서 10진수로의 변환을 하지 않고 문제를 푼 코드입니다.

제 코드의 경우, Runtime은 151ms이고 메모리는 14.1MB를 사용했습니다.

제가 추가로 올려드린 코드의 경우 Runtime은 120ms이고 메모리는 13.8MB를 사용했습니다.

시간과 공간 활용도 모두 linked-list 자체를 활용하여 연산하는 것이 더 좋다는 것을 알 수 있습니다.