Add Two Numbers
https://leetcode.com/problems/add-two-numbers/ (opens in a new tab)
내 풀이
딱히 대단한 풀이랄 것도 없다. 그냥 linked list를 뒤집어서 하나의 str로 만들고 str 끼리 더하고 다시 그 더해진 str을 linked list(역순)으로 만들어주면 끝이다. 그래서 그런지 코드가 너무 더럽다.
from collections import deque
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode :
q1, q2 = deque(), deque()
while l1 or l2 :
if l1 :
q1.appendleft(str(l1.val))
l1 = l1.next
if l2 :
q2.appendleft(str(l2.val))
l2 = l2.next
max_range = max(len(q1), len(q2))
str1 = ""
str2 = ""
for i in range(max_range) :
if i < len(q1) :
str1 = str1 + q1[i]
if i < len(q2) :
str2 = str2 + q2[i]
sum = str(int(str1) + int(str2))
first_node = None
pre_node: ListNode = None
for i in range(len(sum) - 1, -1, -1) :
if pre_node :
pre_node.next = ListNode(val=int(sum[i]))
pre_node = pre_node.next
else :
first_node = ListNode(val=int(sum[i]))
pre_node = first_node
return first_node남의 풀이
carry 사용
초등학교 수준에서 덧셈을 생각해보면 된다. 첫 번째 자리 수를 더하고 올림이 있다면 다음 자리 수를 더할 때 1을 더해주면 된다.
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = cur = ListNode(0)
carry = 0
while l1 or l2 or carry:
if l1:
carry += l1.val
l1 = l1.next
if l2:
carry += l2.val
l2 = l2.next
cur.next = ListNode(carry%10)
cur = cur.next
carry //= 10 # 몫만 저장
return dummy.next