문제 개요
두 개의 비어 있지 않은 연결 리스트가 각각 음수가 아닌 정수를 나타낸다고 가정해 봅시다. 이때 가장 큰 자릿수(최상위 자릿수)가 맨 앞에 오며, 각 노드에는 한 자릿수만 저장되어 있습니다. 우리는 이 두 수를 더한 결과를 다시 연결 리스트 형태로 반환해야 합니다.
예를 들어 [7, 2, 4, 3]과 [5, 6, 4]를 더하면 결과는 [7, 8, 0, 7]이 됩니다. 실제 숫자로 계산하면 7243 + 564 = 7807과 같습니다.
왜 스택을 사용할까?
자릿수가 역순(일의 자리부터)으로 저장되어 있다면 순서대로 더하면 되지만, 이 문제는 최상위 자릿수가 먼저 나오기 때문에 바로 더하기 어렵습니다. 스택의 LIFO(Last In First Out) 특성을 활용하면 모든 노드를 push한 뒤 pop할 때 일의 자리부터 차례대로 꺼낼 수 있어 덧셈을 자연스럽게 처리할 수 있습니다.
알고리즘 접근 방법
- 값이 0인 더미(dummy) 노드를 생성하고, 두 개의 스택 s1과 s2를 준비합니다.
- l1의 모든 노드를 s1에, l2의 모든 노드를 s2에 차례로 push합니다.
- sum := 0으로 초기화합니다.
- s1 또는 s2가 비어 있지 않은 동안 아래 작업을 반복합니다.
- s1이 비어 있지 않으면 sum에 s1의 top 값을 더한 뒤 pop합니다.
- s2가 비어 있지 않으면 sum에 s2의 top 값을 더한 뒤 pop합니다.
- 더미 노드의 값 := sum % 10
- sum / 10의 값을 가지는 새 노드(newNode)를 생성합니다.
- newNode의 next := dummy
- dummy := newNode
- sum := sum / 10
- 반복이 끝난 후 더미 노드의 값이 0이면 dummy->next를 반환하고, 그렇지 않으면 dummy를 그대로 반환합니다.
C++ 구현 예제
아래 코드를 통해 실제 동작 과정을 더 쉽게 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class ListNode{
public:
int val;
ListNode *next;
ListNode(int data){
val = data;
next = NULL;
}
};
ListNode *make_list(vector<int> v){
ListNode *head = new ListNode(v[0]);
for(int i = 1; i<v.size(); i++){
ListNode *ptr = head;
while(ptr->next != NULL){
ptr = ptr->next;
}
ptr->next = new ListNode(v[i]);
}
return head;
}
void print_list(ListNode *head){
ListNode *ptr = head;
cout << "[";
while(ptr){
cout << ptr->val << ", ";
ptr = ptr->next;
}
cout << "]" << endl;
}
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* dummy;
dummy = new ListNode(0);
stack <ListNode*> s1, s2;
while(l1){
s1.push(l1);
l1 = l1->next;
}
while(l2){
s2.push(l2);
l2 = l2->next;
}
int sum = 0;
while(!s1.empty() || !s2.empty()){
if(!s1.empty()){
sum += s1.top()->val;
s1.pop();
}
if(!s2.empty()){
sum += s2.top()->val;
s2.pop();
}
dummy->val = (sum % 10);
ListNode* newNode = new ListNode(sum / 10);
newNode->next = dummy;
dummy = newNode;
sum /= 10;
}
return dummy->val == 0? dummy->next : dummy;
}
};
main(){
vector<int> v1 = {7,2,4,3};
ListNode *h1 = make_list(v1);
vector<int> v2 = {5,6,4};
ListNode *h2 = make_list(v2);
Solution ob;
print_list(ob.addTwoNumbers(h1, h2));
}입력
[7,2,4,3] [5,6,4]
출력
[7, 8, 0, 7]
복잡도 분석
두 리스트의 길이를 각각 n, m이라 하면 시간 복잡도는 O(n + m)입니다. 모든 노드를 한 번씩 스택에 넣고 꺼내며 덧셈을 수행하기 때문입니다. 공간 복잡도 역시 두 스택에 모든 노드를 저장하므로 O(n + m)입니다.