문제 설명
비어 있지 않은 두 개의 연결 리스트(linked list)가 주어졌다고 가정해 보겠습니다. 이 두 리스트는 각각 음수가 아닌 정수를 나타내며, 숫자는 역순(일의 자리부터)으로 저장되어 있습니다. 각 노드에는 한 자릿수만 들어갑니다. 우리의 목표는 이 두 수를 더한 결과를 다시 연결 리스트 형태로 반환하는 것입니다. 단, 숫자 0 자체를 제외하고는 어떤 수도 선행 0(leading zero)을 포함하지 않는다고 가정합니다.
예를 들어 120 + 230을 계산한다면, 연결 리스트로는 [0 → 2 → 1] + [0 → 3 → 2] = [0 → 5 → 3], 즉 350이 됩니다.
해결 알고리즘
이 문제는 손으로 두 숫자를 더할 때처럼 각 자릿수를 차례대로 더하면서 올림수(carry)를 처리하면 해결할 수 있습니다. 단계별로 살펴보겠습니다.
- 두 리스트 l1과 l2를 입력받고, head와 temp를 null로 초기화합니다.
- 올림수 변수 c를 0으로 설정합니다.
- l1 또는 l2 중 하나라도 비어 있지 않은 동안 아래 과정을 반복합니다.
- l1이 비어 있으면 a := 0, 그렇지 않으면 a := l1.val로 설정합니다.
- l2가 비어 있으면 b := 0, 그렇지 않으면 b := l2.val로 설정합니다.
- n := a + b + c를 계산합니다.
- n이 9보다 크면 c := 1, 그렇지 않으면 c := 0으로 설정합니다.
- n mod 10 값을 갖는 새 노드를 생성합니다.
- head가 null이라면 head := node, temp := node로 설정합니다.
- 그렇지 않다면 head.next := node로 연결한 뒤 head := node로 이동합니다.
- l1이 존재하면 다음 노드로 이동합니다.
- l2가 존재하면 다음 노드로 이동합니다.
- 반복이 끝난 후 c가 0이 아니라면(올림수가 남아 있다면) 값이 1인 새 노드를 만들어 결과 리스트의 맨 뒤에 추가합니다.
- temp(결과 리스트의 첫 번째 노드)를 반환합니다.
파이썬 구현 예제
아래 코드를 통해 실제 구현을 더 잘 이해해 보겠습니다.
class ListNode:
def __init__(self, data, next = None):
self.val = data
self.next = next
def make_list(elements):
head = ListNode(elements[0])
for element in elements[1:]:
ptr = head
while ptr.next:
ptr = ptr.next
ptr.next = ListNode(element)
return head
def print_list(head):
ptr = head
print('[', end = "")
while ptr:
print(ptr.val, end = ", ")
ptr = ptr.next
print(']')
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
head = None
temp = None
c = 0
while l1 or l2:
if not l1:
a = 0
else:
a = l1.val
if not l2:
b = 0
else:
b = l2.val
n = a + b + c
c = 1 if n > 9 else 0
node = ListNode(n % 10)
if not head:
head = node
temp = node
else:
head.next = node
head = node
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
if c:
node = ListNode(1)
head.next = node
return temp
ob1 = Solution()
l1 = make_list([0,2,1])
l2 = make_list([0,3,2])
print_list(ob1.addTwoNumbers(l1, l2))
입력
[0,2,1]
[0,3,2]
출력
[0,5,3]
정리
이 알고리즘의 핵심은 숫자가 역순으로 저장되어 있기 때문에 일의 자리부터 차례대로 더할 수 있다는 점입니다. 두 리스트를 동시에 순회하며 각 자릿수의 합과 올림수를 계산하고, 모든 자릿수를 처리한 후에도 올림수가 남아 있다면 마지막에 노드 하나를 추가로 붙여주면 됩니다. 시간 복잡도는 O(max(m, n))(m, n은 각 리스트의 길이)이며, 공간 복잡도는 결과 리스트의 길이에 비례해 O(max(m, n) + 1)입니다.