Add Two Numbers(LeetCode 문제) python 풀이

문제 링크: https://leetcode.com/problems/add-two-numbers/

1. 문제 파악

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.

즉, 두 개의 linked list에 있는 단일 숫자를 역순으로 구한 값을 더하고, 다시 이 수를 역순으로 linked list에 넣어 리턴하는 함수를 만드는 것이다.

1-1. 조건

The number of nodes in each linked list is in the range [1, 100].
0 <= Node.val <= 9
It is guaranteed that the list represents a number that does not have leading zeros.

linked list의 길이는 1이상 100미만이고, 각 노드의 값은 0이상 9이하(1자리수)이다. 그리고 linked list의 마지막 수는 0이 아니다.(Example 2와 같은 경우는 제외)

1-2. 예제

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

2. 풀이

먼저, 나의 풀이를 살펴보겠다.

2-1. 나의 풀이

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        
        l1_reversed = ''
        l2_reversed = ''
        print(l1)
        for i in reversed(l1):
            l1_reversed += str(i)
        
        for j in reversed(l2):
            l2_reversed += str(j)
            
        return int(l1_reversed) + int(l2_reversed)

첫번째는 linked list 말고 단순 list로 생각한 후 먼저 구현을 해보았다. 두 개의 list를 거꾸로 값을 하나 하나 넣어주고, 두 개의 list를 더한 후 다시 거꾸로 list에 넣어준다.

class Solution:
    def to_int(l: ListNode):
        s = ''
        while l != None:
            s += str(l.val)
            l = l.next
        return int(s[::-1])
    
    def to_list(n: int):
        s = str(n)[::-1]
        head = prev = None
        for ch in s:
            node = ListNode(int(ch))
            if prev is not None:
                prev.next = node
            prev = node
            if head is None:
                head = prev
        return head
    
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        a = Solution.to_int(l1)
        b = Solution.to_int(l2)
        return Solution.to_list(a + b)

그리고 위에서 만든 코드를 토대로 int로 바꿔주는 함수 to_int와 list로 바꿔주는 함수 to_list를 만들었다. 그리고 최종적인 결과물을 도출해냈다.

2-2. LeetCode Solution

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        result = ListNode(0)
        result_tail = result
        carry = 0
                
        while l1 or l2 or carry:            
            val1  = (l1.val if l1 else 0)
            val2  = (l2.val if l2 else 0)
            carry, out = divmod(val1+val2 + carry, 10)    
                      
            result_tail.next = ListNode(out)
            result_tail = result_tail.next                      
            
            l1 = (l1.next if l1 else None)
            l2 = (l2.next if l2 else None)
               
        return result.next

위의 코드는 while 문을 사용하여 두 개의 linked list의 값을 서로 하나씩 계산할때마다 넣어주었다. 하지만 런타임은 68초으로 나의 코드보다 낮게 나왔다. 대신 메모리는 나의 코드는 14.3 MB가 나왔지만 이 코드의 경우는 13.5 MB가 나왔다.