[파이썬 알고리즘] 연결 리스트의 두 수 덧셈

연결리스트의 두 수의 덧셈

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

리트코드로 풀러 가기

입력
(2 -> 4 -> 3) + (5 -> 6 -> 4)

출력
7 -> 0 -> 8

---

code: addTwoNumbers.py

이 문제는 자료형을 바꾸어 풀거나, 전가산기를 직접 구현하여 풀 수 있다.

자료형 변환

먼저, 단순하게 접근하여 각 연결 리스트를 형변환 하괴, 더한 뒤 다시 형변환해주면 문제가 풀린다.

1. 각 연결 리스트를 순회하며 int로 형변환을 한다.

2. 형변환된 각 int를 더한다

3. 더한 결과를 연결 리스트로 바꾸어 반환한다.

def addTwoNumbers(self, l1, l2):
    num1 = 0
    num2 = 0

    count = 0
    while l1:
        num1 += l1.val * (10 ** count)
        count+=1
        l1 = l1.next

    count = 0

    while l2:
        num2 += l2.val * (10 ** count)
        count+=1
        l2 = l2.next

    result = str(num1 + num2)

    last = None

    for c in result:
        node = ListNode(c)
        node.next = last
        last = node

    return node

for 문 안에서, node.next를 last가 가리키고, 다음줄에서 last가 node가 되므로, node.next가 바뀌지 않을까 생각할 수 있다.

하지만, node.next는 last가 이전에 가리키고 있던 객체를 참조하기 때문에 바뀌지 않는다.

전가산기 구현

합을 진법으로 나누어서 carry와 val로 나누는 전가산기의 원리를 코드로 옮긴다.

원래 가산기는 논리 회로를 이용해 이진 연산을 수행하지만, 여기서는 전체적인 구조만 참고하였다.

def addTwoNumbers2(self, l1, l2):
    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