8장_16 연결리스트(두 수의 덧셈)

문제: 역순으로 저장된 연결리스트의 숫자를 더하라.

1. 자료형 변환

간단하게 생각한 방법은 연결리스트를 문자열로 이어서 숫자로 변환하고 덧셈을 한 뒤에 다시 연결리스트로 바꾸는 방법인데 문제 의도가 이런 변환 후 또 변환하는 방법은 의도 한 것은 아닐 것 같지만 일단 따라해 봤다.

from typing import List


# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    # 연결 리스트 뒤집기
    def reverseList(self, head: ListNode) -> ListNode:
        node, prev = head, None

        while node:
            next, node.next = node.next, prev
            prev, node = node, next

        return prev

    # 연결 리스트를 파이썬 리스트로 변환
    def toList(self, node: ListNode) -> List:
        list: List = []
        while node:
            list.append(node.val)
            node = node.next
        return list

    # 파이썬 리스트를 연결 리스트로 변환
    def toReversedLinkedList(self, result: str) -> ListNode:
        prev: ListNode = None
        for r in result:
            node = ListNode(r)
            node.next = prev
            prev = node

        return node

    # 두 연결 리스트의 덧셈
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        a = self.toList(self.reverseList(l1))
        b = self.toList(self.reverseList(l2))

        resultStr = int(''.join(str(e) for e in a)) + \
                    int(''.join(str(e) for e in b))

        # 최종 계산 결과 연결 리스트 변환
        return self.toReversedLinkedList(str(resultStr))

def reverseList(self, head: ListNode) -> ListNode:
    node, prev = head, None
    while node:
        next, node.next = node.next, prev
        prev, node = node, next
    return prev

15번에서 했던 리스트를 역순으로 바꾸는식을 동일하게 사용했다.

def toList(self, node: ListNode) -> List:
    list: List = []
    while node:
        list.append(node.val)
        node = node.next
    return list

덧셈을 위한 연결 리스트를 파이썬의 리스트로 변경하고

def toReversedLinkedList(self, result: str) -> ListNode:
    prev: ListNode = None
    for r in result:
        node = ListNode(r)
        node.next = prev
        prev = node
    return node

반대의 연결리스트로 변경하는 함수를 작성

  def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
    a = self.toList(self.reverseList(l1))
    b = self.toList(self.reverseList(l2))
    resultStr = int(''.join(str(e) for e in a)) + \
                int(''.join(str(e) for e in b))

숫자형 리스트를 문자형으로 변경해야 하니까 str(e)로 각 항목을 문자로 변경하고 join으로 합친다. 섯셈을 위해 다시 숫자형이 되어야 하니 int로 변경해야한다. 여기에 a랑 b에 +만 해주면 된다.

실행 시간도 메모리도 적게 먹는 것 같긴 한데 더 간단하고 깔끔한 풀이를 알아보자

2. 전가산기 구현

Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


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

if l1:
            sum += l1.val
            l1 = l1.next
        if l2:
            sum += l2.val
            l2 = l2.next
            carry, val = divmod(sum + carry, 10)

두 입력값의 합을 구한다. 자릿수가 넘어가면 자리 올림을 한다.

divod는 처음 써봤는데 무척 편한 방법같다.
10을 3으로 나누려 한다고 예를 들면 divmod(10,3)를 하면 몫이3 나머지가 1이 나오는데 원래는 몫과 나머지를 따로 구해야 할 것이다.