[알고리즘] 두 수의 덧셈

두 수의 덧셈

내 풀이

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

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        nums1, nums2 = [], []
        while l1 != None:
            nums1.append(str(l1.val))
            l1 = l1.next

        while l2 != None:
            nums2.append(str(l2.val))
            l2 = l2.next

        nums1 = ''.join(nums1[::-1])
        nums2 = ''.join(nums2[::-1])
        ans = int(nums1) + int(nums2)
        ans = [x for x in str(ans)]
        result_head = ListNode()
        tail = result_head
        for i in range(len(ans)-1, -1, -1):
            tail.next = ListNode(int(ans[i]))
            tail = tail.next

        return result_head.next

두 개의 링크드 리스트를 리스트로 변환해서 숫자로 변환하고, 두 숫자를 더해서 다시 링크드 리스트를 만드는 풀이다.

숫자형 리스트를 단일 값으로 병합하기

a = [1, 2, 3, 4, 5]
' '.join(map(str, a))

책 풀이

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        root = head = ListNode(0)

        carry = 0
        while l1 or l2 or carry:
            sum = 0
            if l1:
                sum += l1.val
                l1 = l1.next
            if l2:
                sum += l2.val
                l2 = l2.next

            # 몫과 나머지 계산
            carry, val = divmod(sum + carry, 10)
            head.next = ListNode(val)
            head = head.next

        return root.next

실제 덧셈을 하듯이 뒤에서부터 더해가는 방식이다. 만약 carry가 발생하면 다음 게산에서 그것을 더해준다. divmod 함수는 몫과 나머지로 구성된 튜플을 리턴한다.