“파이썬 알고리즘 인터뷰” + https://leetcode.com/problems/add-two-numbers/
역순으로 연결된 연결 리스트의 숫자를 더한 결과를 연결 리스트로 반환하는 문제이다. l1 = [2,4,3], l2 = [5,6,4] 일 경우 342 + 465 = 807 이므로 [7,0,8] 을 연결 리스트로서 반환해야한다.
덧셈이지만 연결 리스트가 역순으로 배치되어 있는 것과 연결 리스트라는 이유로 자리 올림 같은 것들을 어떻게 할지 생각해야 했다. 먼저 풀이를 보지 않고 생각 나는대로 해결한 것이 addTwoNumbers1()이다. 재귀로 두 연결 리스트의 값을 더하고 자리 올림이 발생하면 다음 함수로 넘겨서 같이 더하게 했다. 잘 시간이 다돼서 적당히 돌아가게만 했더니 군더더기가 많은 코드가 돼버려서 아쉽다. 나중에 나올 전가산기? 방식과 비교해보니 아직 파이썬에 익숙하지 않다는 게 보여서 아쉬웠다.
def addTwoNumbers1(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
def add(l1: ListNode, l2: ListNode, co: int = 0):
if l1 and not l2:
val1, val2 = l1.val, 0
next1, next2 = l1.next, None
elif not l1 and l2:
val1, val2 = 0, l2.val
next1, next2 = None, l2.next
else:
val1, val2 = l1.val, l2.val
next1, next2 = l1.next, l2.next
sum = ListNode((val1 + val2 + co) % 10)
co = (val1 + val2 + co) // 10
if next1 and next2:
sum.next = add(next1, next2, co)
elif next1 and not next2:
sum.next = add(next1, None, co)
elif not next1 and next2:
sum.next = add(None, next2, co)
else:
if co > 0:
sum.next = ListNode(co)
return sum
return add(l1, l2)효율적이지 못한 코드라고 생각했는데 의외로 책에 나온 두 번째 방식과 비슷해서 놀랐다. 코드를 표현하는 방식에서 책에서 말하는 “우아함”이 확연하게 차이 나는 건 별개로.
def addTwoNumbers2(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[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.toReverseLinkedList(str(resultStr))
def reverseList(self, head: ListNode) -> ListNode:
node, prev = head,None
while node:
next, node.next = node.next, prev
prev, node = node, next
return prev
def toList(self, node: ListNode) -> ListNode:
list: List = []
while node:
list.append(node.val)
node = node.next
return list
def toReverseLinkedList(self, result: ListNode) -> ListNode:
prev: ListNode = None
for r in result:
node = ListNode(r)
node.next = prev
prev = node
return nodeaddTwoNumbers2() 는 책의 첫 번째 풀이인데 연결 리스트를 뒤집서 일반 리스트로 바꾸고 리스트의 요소를 통째로 문자열로 만들어 두 수를 더한 결과를 다시 연결 리스트로 만드는 방법이다.
def addTwoNumbers3(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[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.nextaddTwoNumber3() 가 책에 나온 “전가산기 구현”이라는 방식이다. 매우 깔끔하다. 나는 인자로 전달받은 l1과 l2를 그대로 덮어쓰는 방식에 익숙하지 않아서 따로 변수로 만들어 저장했는데. 그리고 몫과 나머지를 한꺼번에 구하는 내장 함수 divmod()를 처음 알았다. 자주 쓰이는 계산이니 기본 함수로 있어도 이상하지 않다. 또 나는 반복보다 재귀를 활용하는 경향이 있는데 위와 같은 반복이 덜 헷갈려서 좋아보인다.