문제 개요
두 개의 단일 연결 리스트(singly linked list) L1과 L2가 있다고 가정해 봅시다. 각 리스트는 숫자를 최하위 자릿수(일의 자리)부터 앞쪽에 배치하여 표현합니다. 우리가 해야 할 일은 이 두 숫자를 더한 결과를 담은 새로운 연결 리스트를 만드는 것입니다.
예를 들어 입력이 다음과 같다고 해보겠습니다.
- L1 = [5, 6, 4] → 숫자 465
- L2 = [2, 4, 8] → 숫자 842
이 경우 465 + 842 = 1307이므로, 출력은 [7, 0, 3, 1]이 됩니다.
해결 접근 방법
이 문제는 마치 손으로 두 숫자를 더할 때처럼, 일의 자리부터 차례대로 더해 가면서 올림수(carry)를 관리하면 됩니다. 알고리즘은 다음과 같습니다.
- 올림수 carry를 0으로 초기화합니다.
- 값이 0인 더미(dummy) 노드 res를 만들고, 현재 위치를 가리키는 포인터 curr을 res로 설정합니다.
- L1 또는 L2에 노드가 남아 있거나, 올림수가 0이 아닌 동안 다음을 반복합니다.
- L1이 비어 있지 않으면 L1의 값을, 비어 있으면 0을 사용합니다.
- L2도 마찬가지로 값이 있으면 해당 값을, 없으면 0을 사용합니다.
- 두 값을 더한 뒤 기존 올림수를 함께 더합니다.
- 그 합을 10으로 나눈 몫은 새로운 올림수로, 나머지는 결과 자릿수로 사용합니다.
- 결과 자릿수 값을 가진 새 노드를 curr 뒤에 연결하고, curr을 한 칸 앞으로 이동시킵니다.
- L1과 L2가 남아 있다면 각각 다음 노드로 이동시킵니다.
- 반복이 끝나면 더미 노드의 다음 노드(res.next)를 반환합니다.
파이썬 코드 구현
아래 코드를 통해 실제 동작 과정을 확인해 보겠습니다.
예제 코드
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 solve(self, L1, L2):
carry = 0
res = ListNode(0) # 더미 헤드 노드
curr = res
while L1 or L2 or carry:
val1 = L1.val if L1 else 0
val2 = L2.val if L2 else 0
total = val1 + val2
# divmod(): 몫은 올림수, 나머지는 결과 자릿수
carry, add_val = divmod(total + carry, 10)
curr.next = ListNode(add_val)
curr = curr.next
L1 = L1.next if L1 else None
L2 = L2.next if L2 else None
return res.next
ob = Solution()
L1 = make_list([5, 6, 4])
L2 = make_list([2, 4, 8])
print_list(ob.solve(L1, L2))
입력
[5,6,4], [2,4,8]
출력
[7, 0, 3, 1]
핵심 포인트 정리
- 더미 노드 활용: 값이 0인 더미 노드를 미리 만들어 두면, 결과 리스트의 첫 노드 삽입 로직을 일반화할 수 있어 코드가 훨씬 깔끔해집니다.
- divmod() 함수: 파이썬의 divmod(x, 10)는 몫과 나머지를 한 번에 반환하므로, 올림수 계산 코드를 간결하게 작성할 수 있습니다.
- 반복 종료 조건: 두 리스트가 모두 끝났더라도 올림수가 남아 있으면(예: 999 + 1) 추가 자릿수를 만들어야 하므로, 조건에 carry 검사를 반드시 포함해야 합니다.
복잡도 분석
- 시간 복잡도: O(max(m, n)) — 두 리스트 중 더 긴 쪽의 길이만큼 한 번씩 순회합니다.
- 공간 복잡도: O(max(m, n)) — 결과를 저장할 새로운 연결 리스트가 필요합니다.