Algorithm Study/leetcode
[LeetCode] 2. 두 수의 덧셈(Add Two Numbers)
오패산개구리
2021. 7. 3. 14:49
728x90
반응형
역순으로 저장된 연결 리스트의 숫자를 더하라.
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.
1. 자료형 변환
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
# 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))
|
cs |
해설:
단순하게 우리가 생각하는 그 방법.
역순으로 저장되어 있으니 연결 리스트를 뒤집어주고
연결 리스트의 값을 더해줘야 하니까 파이썬 리스트로 변환시켜 준다.
그리고 두 파이썬 리스트를 int로 변환하여 더해준 다음
다시 역순 연결 리스트로 바꿔준다.
2. 전가산기 구현
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
# 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
|
cs |
해설:
1번 풀이와 달리 우아한 풀이이다.
carry라는 변수를 두고 sum이 10 이상일 경우 올림수로 carry=1이 입력된다.
그리고 다음 while문 반복에 sum+carry 부분을 통해 올림수를 더해준다.
출처: 파이썬 알고리즘 인터뷰(박상길 지음, 정진호 일러스트) 출판사[책만]
728x90
반응형