연결 리스트¶

두 수의 덧셈¶

https://leetcode.com/problems/add-two-numbers/

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

입력 :

(2 -> 4 -> 3) + (5 -> 6 -> 4)

출력 :

7 -> 0 -> 8

설명 : 342 + 465 = 807

In [1]:

from typing import List 

In [2]:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next        

In [18]:

def printLinkedList(head: ListNode):
    while head:
        print(head.val)
        head = head.next

In [32]:

node_3 = ListNode(3)
node_2 = ListNode(4, node_3)
node_1 = ListNode(2, node_2)

node_6 = ListNode(4)
node_5 = ListNode(6, node_6)
node_4 = ListNode(5, node_5)

In [16]:

def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:
    num1 = ''
    num2 = ''
    while l1:
        num1 = str(l1.val) + num1
        l1 = l1.next
    
    while l2:
        num2 = str(l2.val) + num2
        l2 = l2.next
    
    s = int(num1) + int(num2)
    
    s_l = list(str(s))
    
    cur = None
    for x in s_l:
        nxt = ListNode(x, cur)
        cur = nxt
    
    return cur

In [19]:

printLinkedList(addTwoNumbers(node_1, node_4))

7
0
8

Accepted	72 ms	14.4 MB	python3

풀이 1. 자료형 변환¶

In [20]:

def reverseList(head: ListNode) -> ListNode:
    node, prev = head, None
    
    while node:
        next, node.next = node.next, prev
        prev, node = node, next
        
    return prev

In [21]:

def toList(node: ListNode) -> ListNode:
    list: List = []
    while node:
        list.append(node.val)
        node = node.next
    return list

In [22]:

def toReversedLinkedList(result: str) -> ListNode:
    prev: ListNode = None
    for r in result:
        node = ListNode(r)
        node.next = prev
        prev = node

In [28]:

def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:
    a = toList(reverseList(l1))
    b = toList(reverseList(l2))

    resultStr = int(''.join(str(e) for e in a)) + \
                int(''.join(str(e) for e in b))

    return toReversedLinkedList(str(resultStr))

In [29]:

printLinkedList(addTwoNumbers(node_1, node_4))

Accepted	84 ms	14.4 MB	python3

풀이 2. 전가산기 구현¶

In [30]:

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

In [33]:

printLinkedList(addTwoNumbers(node_1, node_4))

7
0
8

Accepted	72 ms	14.3 MB	python3

숫자형 리스트를 단일 값으로 병합하기¶

In [34]:

a = [1, 2, 3, 4, 5]

In [35]:

''.join(str(e) for e in a)

Out[35]:

'12345'

In [36]:

''.join(map(str, a))

Out[36]:

'12345'

In [37]:

import functools

In [41]:

functools.reduce(lambda x, y: 10 * x + y, a, 0)

Out[41]:

In [42]:

from operator import add, mul

In [43]:

functools.reduce(add, a)

Out[43]:

In [44]:

functools.reduce(mul, a)

Out[44]: