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

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

역순으로 저장된 연결리스트의 숫자 덧셈

 

책에서 구현된 코드

def addTwoNumbers(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

 

기억해야할 기법

• 두 연결리스트의 길이가 다를 경우
  • next의 값을 가져올 때, 가져오는 구문을 분리
    if l1
    if l2
• 결과의 새로운 리스트 만들기
  • 공간복잡도는 생각하느라 하나의 리스트에 합을 만드려고함
  • 마지막 carry로 인한 새로운 노드를 추가하는 구문에서 복잡성이 증가
  • 차라리 결과를 새로운 리스트로 만드는 것이 깔끔 (carry가 있는지만 확인한 후 새로 추가하면 됨)

 

내가 구현한 코드

# 동작하지않음
def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:
    def add(one: ListNode, two: ListNode, carry: int = 0):
        if not one and not two:
            return l1
        if not one:
            one, two = two, one
        val1 = one.val
        val2 = two.val if two else 0

        crnt_val = val1 + val2 + carry
        one.val = crnt_val % 10

        if two:
            two = two.next
        if not one.next:
            one.next = two
            two = None
        return add(one.next, two, crnt_val // 10)

• 복잡하게 생각하여 if문 천치가 됨 (중도포기)
• 코드가 깔끔하지 않다면 정답이 아니라고 생각해야함