알고리즘 | Algorithm

[LeetCode 리트코드] Add Two Numbers, python 파이썬

개발자R 2021. 1. 12. 18:29
반응형

문제

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.

0이상의 정수로 이루어진 linked list 두 개가 주어진다. 각 노드의 값은 한 자리 숫자이다. linked list는 거꾸로된 방향으로 각 자리가 저장되어있다. 이 두개의 숫자를 더한 linked list를 리턴하라.

예를 들어, l1 = [2,4,3], l2 = [5,6,4] 라면 342 + 465 = 807 이므로 [7, 0, 8]을 리턴

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

output : [7,0,8]

추가사항

 

  • 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. (0으로 시작하지 않음)

 

 

나의 솔루션

# 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:
resultNode = ListNode()
num1 = num2 = ''
while l1:
num1 += str(l1.val)
l1 = l1.next
while l2:
num2 += str(l2.val)
l2 = l2.next
result = str(int(num1[::-1]) + int(num2[::-1]))
curr = resultNode
for s in result[::-1]:
curr.next = ListNode()
curr = curr.next
curr.val = int(s)
return resultNode.next

 

설명

애초에 linked list를 숫자로 변환한 다음, 두 숫자를 더해주고 그걸 다시 linked list로 반대로 넣었다. 물론 출제의 의도는 이건 아닌거같다. ㅎㅎ;;

결과

Submission Detail

 

역시나 조금 느린 편이다.

그래서 출제 의도로 다시 풀어보았다.

# 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:
result = ListNode()
curr = result
carry = 0 #올림 자리 보관
while l1 or l2 or carry:
curr.next = ListNode()
curr = curr.next
num1 = num2 = 0
if l1 :
num1 = l1.val
l1 = l1.next
if l2 :
num2 = l2.val
l2 = l2.next
curr.val = (num1 + num2 + carry) % 10
carry = (num1 + num2 + carry) // 10
return result.next

결과

큰 차이가 없다....ㅎㅎ 뭐한거지?

반응형