16. Add Two Numbers

🎯 leetcode - 2. Add Two Numbers

---

📌 문제

- 파이썬 알고리즘 인터뷰 16번 문제
- 링크드 리스트로 저장된 두 수의 덧셈 결과를 링크드 리스트로 리턴하시오.

📌 날짜

2020.01.25

📌 시도 횟수

풀이 1: 4 try
풀이 2: 1 try

---

🤔 나의 풀이 1

💡 Code

class Solution:
    def list2node(self, result: List) -> ListNode:
        head = result_node = ListNode()
        for num in result:
            result_node.next = ListNode(num)
            result_node = result_node.next
        return head.next

    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        carry = 0
        result = []

        while l1 and l2:
            result.append((l1.val + l2.val) % 10 + carry)
            carry = int((l1.val + l2.val) / 10)
            l1 = l1.next
            l2 = l2.next
        while l1:
            result.append((l1.val + carry) % 10)
            carry = int(((l1.val) % 10 + carry) / 10)
            l1 = l1.next
        while l2:
            result.append((l2.val + carry) % 10)
            carry = int(((l2.val) % 10 + carry) / 10)
            l2 = l2.next

        for i in range(len(result) - 1):
            if result[i] >= 10:
                num = result[i]
                result[i] = num % 10
                result[i + 1] += int(num / 10)

        if result[-1] >= 10:
            num = result[-1]
            result[-1] = num % 10
            result.append(int(num / 10))

        if carry > 0:
            result.append(carry)
        return self.list2node(result)

💡 문제 해결 방법

- 먼저 연산은 두 연결리스트의 각 노드에 차례대로 접근하면서 계산해주었다.
- 단, 결과 값은 result라는 list를 따로 만들어서 결과를 저장했다.
- 이때 carry가 발생하는 경우를 모두 처리해주어 올림 값이 정상적으로 계산되도록 처리했다.
- ListNode를 리턴해주어야 하므로 list2node라는 함수를 추가하여 변환했다.
- 최종적으로 변환한 연결리스트의 head node를 리턴해주었다.

❌ (한번에 맞추지 못한 경우) 오답의 원인

- 마지막에 carry가 남는 경우를 처리하지 않아 오류가 발생했다.
따라서 코드의 끝에 carry가 여전히 남아있는 경우를 다음과 같이 처리해주었다.
>>> 	if carry > 0:
>>> 	result.append(carry)

---

🤔 나의 풀이 2

💡 Code

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        num1, num2 = 0, 0
        i = 0
        while l1:
            num1 += ((l1.val) % 10) * pow(10, i)
            i += 1
            l1 = l1.next
        i = 0
        while l2:
            num2 += ((l2.val) % 10) * pow(10, i)
            i += 1
            l2 = l2.next

        result = str(num1 + num2)[::-1]
        return self.list2node(result)

    def list2node(self, result: List) -> ListNode:
        head = result_node = ListNode()
        for num in result:
            result_node.next = ListNode(num)
            result_node = result_node.next
        return head.next

💡 문제 해결 방법

- 각각의 연결 리스트를 정수로 변환하여 계산했다. 
- pow(거듭제곱)를 이용하여 각 자릿수를 고려한 정수값을 계산할 수 있었다.
- 변환 후 두개의 값을 더하여 최종 값을 계산했다.
- 정수형을 문자열로 변환하고, [::-1]을 이용하여 문자열을 뒤집었다.
- 이렇게 뒤집힌 문자열을 list2node 함수에 넣어 다시 링크드 리스트로 변환하여 리턴했다.

• ㅎㅎ 정말 비효율적인 코드이다. ^^

---

😉 다른 풀이

📌 하나. 자리올림수(carry) 이용하기👍👍

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

💡 새롭게 알게 된 점

- 정말 예쁜 풀이인 것 같다🥺
- while문의 조건을 or로 처리하고 각각의 case를 if l1, if l2로 처리하는 게 정말 깔끔한 것 같다.

divmod(a, b)

• 몫과 나머지로 구성된 튜플을 리턴한다.
• 즉, (a // b, a % b)와 동일한 결과를 리턴한다.
• 따라서 위 코드에서는 각각 올림수(carry), 출력값(val)에 저장했다.

---

📌 둘. 자료형 변환하여 구하기 (참고)

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 list2node(self, list1: List):
        head = result_node = ListNode()
        for num in list1:
            result_node.next = ListNode(num)
            result_node = result_node.next
        return head.next

    def node2list(self, node1: ListNode):
        list1 = []
        while node1 != None:
            list1.append(node1.val)
            node1 = node1.next
        return list1

    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        a = self.node2list(self.reverseList(l1))
        b = self.node2list(self.reverseList(l2))

        result_str = int("".join(str(e) for e in a)) + int("".join(str(e) for e in b))
        return self.list2node(str(result_str)[::-1])

💡 새롭게 알게 된 점

- 앞 문제(15번)에서 배운 뒤집힌 연결리스트 방법을 활용했다.
- ''.join(str) 방법을 이용해서 문자열을 조작했다.