[Leetcode] 리트코드 - 두 수의 덧셈(add-two-numbers) 파이썬(python) 풀이

두 수의 덧셈

문제

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

입력
(2 → 4 → 3) + (5 → 6 → 4)

출력
7 → 0 → 8

코드

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

풀이

논리 회로의 전가산기(Full Adder)와 유사한 형태로 구현하면 이진법이 아니라 십진법이라는 차이만 있을 뿐, 자리올림수(Carry)를 구하는 것까지 가산기의 원리와 거의 동일하다. 전 가산기의 진리표와 회로도는 다음 그림과 같다.

입력값 A, B 이전의 자리올림수(Carry in) 이렇게 3가지 입력으로 합(Sum)과 다음 자리올림수(Carry out)여부를 결정한다. 입력값 A, B는 오른쪽으로는 XOR 게이트를 통과한 결과가 나아가고, 아래로는 AND 게이트를 통과한 결과가 나아간다. 그렇게 합과 다음 자리올림수 위치에 도달한 결과가 그림 좌측의 진리표다.

여기서는 연산 결과로 나머지를 취하고 몫은 자리올림수 형태로 올리는 전가산기의 전체적인 구조만 참고해 풀이한다.

이 코드에서 먼저, 두 입력값의 합을 구한다. l1, l2는 그림의 오른쪽 전가산기 회로도에서 A, B의 역할과 동일하다. 두 입력값의 연산을 수행하고 다음과 같이 자릿수가 넘어갈 경우에는 자리올림수를 설정할 것이다.

carry, val = divmod(sum + carry, 10)

이처럼 자리올림수를 계산하게 되는데, 전가산기와 마찬가지로 이전의 자리올림수 carry를 받아오고, 이를 divmod()로 계산한다.

가산 결과가 두 자릿수가 될 경우 몫은 자리올림수로 설정해 다음번 연산에 사용되게 하고 나머지는 값으로 취한다. 이제 이 값을 연결 리스트로 만들어 주면 된다.

출처
파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]