[LeetCode]Add Two Numbers

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

Add Two Numbers - LeetCode

 

문제 분석

두개의 숫자 리스트 노드가 주어질 때 더하는 문제입니다.

 

처음 시도한 답안

# Definition for singly-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]:
        l1_numbers = []
        l2_numbers = []
        while l1:
            l1_numbers.append(str(l1.val))
            l1 = l1.next

        while l2:
            l2_numbers.append(str(l2.val))
            l2 = l2.next

        l1_numbers.reverse()
        l2_numbers.reverse()
        
        l1_number = int(''.join(l1_numbers))
        l2_number = int(''.join(l2_numbers))

        number_sum = l1_number + l2_number
        number_sum2 = ''.join(reversed(list(str(number_sum))))

        cur = dummy = ListNode()
        for idx, number in enumerate(str(number_sum2)):
            dummy.val = int(number)
            if idx + 1 == len(number_sum2):
                break
            dummy.next = ListNode()
            dummy = dummy.next


        return cur

접근 방법

1. l1, l2를 순회하고 각각의 숫자를 뒤집습니다.
2. 뒤집은 두개의 숫자를 서로 더하고 다시 뒤집습니다.
3. cur, dummy 2개의 링크드 리스트를 활용해 뒤집은 숫자(문자)를 순회하면서 링크드 리스트를 생성합니다.

정말 직관적으로 접근했던 방법입니다. 문제에서 설명하는 것을 구현하기 위해 두 링크드 리스트를 뒤집고 더한 후 그 숫자를 활용하는 방식입니다. 하지만, 코드를 보면 알 수 있듯이 여러번의 반복, 자주 뒤집고 심지어 형 변환까지 하고있어 굉장히 비 효율적으로 보입니다.

그래서 다른 분들의 답안을 참고해서 최적화 해보았습니다.

 

두번째로 시도한 답안 

# Definition for singly-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]:
        carry = 0
        root = dummy = ListNode(0)
        while l1 or l2 or carry:
            if l1:
                carry += l1.val
                l1 = l1.next
            if l2:
                carry += l2.val
                l2 = l2.next

            carry, val = divmod(carry, 10)
            dummy.next = ListNode(val)
            dummy = dummy.next
            
        return root.next

접근 방법

1. l1, l2, carry가 모두 값이 없을때까지 반복합니다. carry는 올림수의 역할을 합니다.
2. l1에 값이 존재한다면 carry에 val 값을 더하고 다음 노드로 넘깁니다.
3. l2에 값이 존재한다면 carry에 val 값을 더하고 다음 노드로 넘어갑니다.
4. carry를 10으로 나누어 목과 나머지를 구합니다. 여기서 몫은 다음 자릿수에 더하는 용도로 이용이 됩니다. 즉, 올림이 발생한 것입니다. 나머지는 노드의 값으로 설정합니다.

가장 중요한 포인트는 올림수라는 것을 활용하여 값을 더하고 올림수는 다음번 덧셈에 활용하고 나머지는 노드의 값으로서 할당하는 방법입니다. 이렇게 한다면 뒤집거나 여러번 순회할 필요없이 한번의 반복으로 연산을 마칠 수 있습니다.

 

또한, 마지막에 올림수만 존재하는 경우도 커버할 수 있습니다. (carry가 있을 때까지 반복하므로)

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]

Output: [8,9,9,9,0,0,0,1]

 

carry를 활용하는 방법으로 이진수끼리의 덧셈 문제에서도 똑같은 방법으로 풀이할 수 있습니다.