[알고리즘] Add Two Numbers

Leetcode의 Two Sum 문제를 풀어보도록 하겠습니다.

문제

양의 정수를 나타내는 두 개의 비어있지 않은 링크드 리스트가 주어졌다.
각 노드는 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 문을 사용합니다.
간결한 구현을 위해서 결과값을 저장하기 위한 링크드 리스트에는 더미 헤더를 사용하였습니다.
(링크드 리스트를 사용하는 알고리즘 문제에서 자주 사용되는 패턴이기 때문에 익숙해지시면 좋습니다.)

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None

class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode(-1)
node = dummy
carry = 0
while l1 or l2:
num1, num2 = l1.val if l1 else 0, l2.val if l2 else 0
carry, summ = divmod(num1 + num2 + carry, 10)
node.next = ListNode(summ)
node = node.next
if l1:
l1 = l1.next
if l2:
l2 = l2.next
if carry:
node.next = ListNode(carry)
return dummy.next

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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))
  • 공간: O(max(M + N))

하나의 루프를 사용하고 있기 때문에, 알고리즘은 실행 시간은 둘 중에 어느 링크트가 더 긴지에 좌우됩니다.
결과값을 저장하기 위해서 추가적으로 링크드 리스트를 생성해서 사용하며 이 링크드 리스트의 노드의 수는 두 개의 입력 링크드 리스트 중 큰 겂과 동일하거나 carry 발생 시 하나 더 크게 됩니다.

문제 출처

공유하기