[LeetCode] 2. 두 수의 덧셈(Add Two Numbers)

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

 

Input: l1 = [2,4,3], l2 = [5,6,4]

Output: [7,0,8]

 

Explanation: 342 + 465 = 807.

 

 

 

1. 자료형 변환

 

 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: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 = []
        while node:
            list.append(node.val)
            node = node.next
        return list
 
    def toReversedLinkedList(self, result:str)->ListNode:
        prev = 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))

 

해설:

 

단순하게 우리가 생각하는 그 방법.

역순으로 저장되어 있으니 연결 리스트를 뒤집어주고

연결 리스트의 값을 더해줘야 하니까 파이썬 리스트로 변환시켜 준다.

 

그리고 두 파이썬 리스트를 int로 변환하여 더해준 다음

다시 역순 연결 리스트로 바꿔준다.

 

 

 

 

2. 전가산기 구현

 

 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
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

 

해설:

 

1번 풀이와 달리 우아한 풀이이다.

 

전가산기를 알고 있는가?

 

carry라는 변수를 두고 sum이 10 이상일 경우 올림수로 carry=1이 입력된다.

 

그리고 다음 while문 반복에 sum+carry 부분을 통해 올림수를 더해준다.

 

 

 

 

 

 

출처: 파이썬 알고리즘 인터뷰(박상길 지음, 정진호 일러스트) 출판사[책만]