Python 알고리즘 인터뷰 - 문제16. 두수의 덧셈
leetcode - Add Two Numbers https://leetcode.com/problems/add-two-numbers/description/
역순으로 저장된 연결 리스트의 숫자를 더하라
예제
입력
(2->4->3) + (5->6->4)
출력
7->0->8
설명
342 + 465 = 807
풀이
뒷 부분부터 순차적으로 더하기
리스트의 뒷부분으로 순차적으로 더한 후 결과값을 생성 후 노드를 생성하여 연결하는 방법으로 진행한다. 먼저 l1, l2 head 노드부터 시작하여 서로 더한다. 현재 노드의 위치를 cur_l, 새로 생성한 노드를 new_l, 리스트의 시작 노드를 head라고 했을 때 다음과 같이 진행된다.
코드는 다음과 같다.
v = l1.val + l2.val + adder
new_l = ListNode(v)
if not cur_l:
head = new_l
cur_l = new_l
l1, l2를 다음으로 이동하고 두 값을 더했을 때 값이 10이 넘을 경우 v = v % 10을 통해 나머지만 저장하고 adder = 1로 한다.
이후 cur_l.next = new_l을 통해 다음 노드로 연결한 후 cur_l을 new_l로 이동시킨다.
동일하게 l1, l2위치를 이동시킨 후 값 계산 및 노드 연결 및 이동을 진행한다. 마지막 노드에 위치할 경우 head를 반환한다.
계산값이 v가 10을 넘지 않으면 adder를 0으로 변경하여 아래와 같이 다음 노드 계산에는 영향을 주지 않도록 한다.
이를 코드로 나타내면 다음과 같다.
v = l1.val + l2.val + adder
if v >= 10:
v = v % 10
adder = 1
else:
adder = 0
new_l = ListNode(v)
if not cur_l:
head = new_l
else:
cur_l.next = new_l
cur_l = new_l
만약 리스트의 길이가 서로 다르면 노드가 존재하는 곳을 기준으로 adder와 더한 값으로 노드를 생성 및 연결한다.
l = None
if l1:
l = l1
elif l2:
l = l2
while l:
v = l.val + adder
if v >= 10:
v = v % 10
adder = 1
else:
adder = 0
new_l = ListNode(v)
if cur_node:
cur_l.next = new_l
else:
head = new_l
cur_l = new_l
l = l.next
마지막 노드의 합의 결과가 10이 넘는 경우 adder는 1이 되고 이를 다음 리스트에 추가해야한다.
if adder > 0:
cur_l.next = ListNode(1)
전체 코드는 다음과 같다.
def addTwoNumbers(self, l1, l2):
adder = 0
cur_node = None
head = None
#l1, l2 합 처리
while l1 and l2:
v = l1.val + l2.val + adder
if v >= 10:
v = v % 10
adder = 1
else:
adder = 0
new_node = ListNode(v)
if cur_node:
cur_node.next = new_node
else:
head = new_node
cur_node = new_node
l1 = l1.next
l2 = l2.next
#노드의 길이가 다를 경우 adder와 합 처리
l = None
if l1:
l = l1
elif l2:
l = l2
while l:
v = l.val + adder
if v >= 10:
v = v % 10
adder = 1
else:
adder = 0
new_node = ListNode(v)
if cur_node:
cur_node.next = new_node
else:
head = new_node
cur_node = new_node
l = l.next
# 마지막에 adder > 0인 경우 '1' 값의 리스트 연결
if adder > 0:
cur_node.next = ListNode(1)
return head
좀 더 우아하게 구현하기
위의 코드보다 좀 더 우아하게 코드를 작성하도록 구조를 수정해본다.
먼저 결과 노드를 반환할 때 root node를 ListNode(0)을 가리키고 설정하고 리스트 연결이 완료된 후 root.next를 반환하면 덧셈 결과의 노드의 시작점을 가져올 수 있다.
코드로 나타내면 다음과 같다.
def addTwoNumber(l1, l2):
root = head = ListNode(0)
#덧셈 연산 진행
...
return root.next
두 리스트 노드의 덧셈의 값이 10이 넘을 때의 자리올림수를 carry라고 하고 나머지를 val이라고 했을 때 python에서는 divmod 함수를 사용하여 몫, 나머지를 한번에 구할 수 있다. 코드는 다음과 같다.
sum = 5 + 7
# carry = 12 / 10 = 1, val = 12 % 10 = 2
# carry = 1, val = 2
carry, val = divmod(sum, 10)divmod는 몫, 나머지를 튜플로 묶어서 한번에 출력한다.
또한 loop의 조건 중 l1 or l2 or carry 을 만족하는 동안 진행하고 loop내에서 l1, l2의 None체크를 하여 sum을 계산하면 코드를 훨씬 간소화할 수 있다.
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.nextsum = 0 으로 초기화한 후 l1, l2가 존재할 경우 sum에 값을 더하고 다음 노드로 이동하는 방법으로 진행된다. l1, l2 중 하나가 마지막 노드에 도착했을 때(=노드 값이 None)는 덧셈을 진행하지 않으므로 길이가 l1, l2 길이가 달라도 문제없이 동작한다.
이 후 sum + carry 값을 divmod 함수를 통해 carry, val로 분리하며, val값으로 노드를 생성하여 현재 head의 다음 노드로 연결하며, 현재 head 노드를 다음으로 이동시킨다.
carry가 1인 경우에 루프 조건을 만족시키며 진행하므로 마지막 노드에 1을 추가하여 연결하는 것도 문제 없이 진행된다.
전체 코드는 다음과 같다.
def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:
head = root = 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