LeetCode의 Add Two Numbers 문제를 함께 풀어보도록 하겠습니다.
문제
양의 정수를 나타내는 두 개의 비어있지 않은 링크드 리스트가 주어졌다.
각 노드는 1자리 숫자(0…9)를 담고 있고 숫자들은 역순으로 저장되어 있다.
이 링크드 리스트에 저장되어 있는 두 개의 수를 더한 값을 링크드 리스트에 역순으로 저장하여 반환하라.
숫자 0을 제외하고는 두개의 수 앞에는 위치한 불필요한 0은 없는 걸로 간주해도 된다.
예제
- 첫 번째 입력: 2 -> 4 -> 3
- 두 번째 입력: 5 -> 6 -> 4
- 출력: 7 -> 0 -> 8
수가 역순으로 링크드 리스트에 저장되어 있기 때문에 첫 번째 링크드 리스트는 342를 나태나고, 두 번째 링크드 리스트는 465를 나타냅니다.
이 두수를 더하면 807이 나오는데, 이를 다시 역순으로 링크드 리스트에 저장하면 7 -> 0 -> 8이 됩니다.
풀이
링크드 리스트에 수가 역순으로 저장이 되어 있기 때문에 head는 일의 자리의 숫자를 가리키고, head.next는 십의 자리의 숫자를 가리키며, head.next.next는 백의 자리의 숫자를 가리킵니다.
따라서 두 개의 링크드 리스트를 동시에 루프를 돌면서 처음부터 끝까지 두 개의 숫자를 차례로 더해나가면 어렵지 않게 두 수의 합을 구할 수 있습니다.
이 때, 주의할 점은 두 숫자를 더한 값이 10보다 클 경우, carry(올림수)가 발생하며 그 다음 두 숫자를 더할 때 carry 값도 더해줘야 합니다.
풀이
두 개의 링크드 리스트에 각각 몇 개의 노드가 있는지 알 수 가 없기 때문에 루프를 돌릴 때 while 문을 사용합니다.
간결한 구현을 위해서 결과값을 저장하기 위한 링크드 리스트에는 더미 헤더를 사용하였습니다.
(링크드 리스트를 사용하는 알고리즘 문제에서 자주 사용되는 패턴이기 때문에 익숙해지시면 좋습니다.)
먼저 파이썬으로 구현해보겠습니다.
# Definition for singly-linked list.class ListNode:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def addTwoNumbers(
self, l1: Optional[ListNode], l2: Optional[ListNode]
) -> Optional[ListNode]:
node = dummy = ListNode(-1)
carry = 0
while l1 or l2:
summ = l1.val if l1 else 0 + l2.val if l2 else 0
carry, digit = divmod(summ + carry, 10)
node.next = ListNode(digit)
node = node.next
if l1:
l1 = l1.next
if l2:
l2 = l2.next
if carry:
node.next = ListNode(carry)
return dummy.next너무 많은 널(null) 체크를 선호하지 않으시다면, 다음과 같이 살짝 다르게 코드를 작성할 수도 있는데요.
첫 번째 while 문에서는 두 개의 입력 링크드 리스트에 둘 다 노드가 남아있는 동안 동시 순회하고,
두 번째 while 문에서는 두 개의 입력 링크드 리스트 중 더 노드가 많은 링크드 리스트를 상대로만 추가 순회를 하고 있습니다.
class Solution:
def addTwoNumbers(
self, l1: Optional[ListNode], l2: Optional[ListNode]
) -> Optional[ListNode]:
node = dummy = ListNode(-1)
carry = 0
while l1 and l2:
carry, digit = divmod(l1.val + l2.val + carry, 10)
node.next = ListNode(digit)
l1, l2, node = l1.next, l2.next, node.next
l = l1 or l2
while l:
digit = divmod(l.val + carry, 10)
node.next = ListNode(digit)
l, node = l.next, node.next
if carry:
node.next = ListNode(carry)
return dummy.next이번에는 같은 알고리즘을 자바로도 구현해볼까요?
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode node = dummy;
int carry = 0;
while (l1 != null || l2 != null) {
int num1 = l1 != null ? l1.val : 0;
int num2 = l2 != null ? l2.val : 0;
int summ = num1 + num2 + carry;
node.next = new ListNode(summ % 10);
node = node.next;
carry = summ / 10;
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
if (carry > 0) node.next = new ListNode(carry);
return dummy.next;
}
}복잡도
M과 N을 각각 첫 번째, 두 번째 링크드 리스트 내의 노드 수라고 했을때, 시간 복잡도와 공간 복잡도는 모두 O(max(M + N))이 되는데요.
하나의 루프를 사용하고 있기 때문에, 알고리즘은 실행 시간은 둘 중에 어느 링크트 리스트가 더 긴지에 좌우됩니다.
결과값을 저장하기 위해서 추가적으로 링크드 리스트를 생성하는데 이 링크드 리스트 내의 노드의 수는 두 개의 입력 링크드 리스트 중 큰 겂과 동일하거나 carry 발생 시 하나 더 크게 됩겠죠?