문제 개요
자릿수(digit)가 저장된 두 개의 연결 리스트(Linked List)가 주어졌을 때, 이 리스트들이 나타내는 두 숫자를 곱하는 문제입니다. 각 연결 리스트에서 숫자를 만들어 낸 뒤 곱하면 되므로 비교적 간단하게 해결할 수 있습니다. 예제를 통해 살펴보겠습니다.
입력
1 -> 2 -> NULL
2 -> 3 -> NULL
출력
2 -> 7 -> 6 -> NULL
첫 번째 연결 리스트는 12, 두 번째 연결 리스트는 23을 나타내며, 두 수를 곱한 결과인 276이 출력됩니다.
알고리즘
- 두 개의 연결 리스트를 초기화합니다.
- 두 숫자를 저장할 변수를 각각 0으로 초기화합니다.
- 두 연결 리스트를 순회하면서 각 자릿수를 해당 숫자 변수의 뒤에 하나씩 추가합니다.
- 완성된 두 숫자를 곱한 결과를 별도의 변수에 저장합니다.
- 결과값의 각 자릿수를 이용해 새로운 연결 리스트를 생성합니다.
- 새로 만든 연결 리스트를 출력합니다.
C++ 구현
다음은 위에서 설명한 알고리즘을 C++로 구현한 코드입니다.
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
void addNewNode(struct Node** head, int new_data) {
struct Node* newNode = new Node;
newNode->data = new_data;
newNode->next = *head;
*head = newNode;
}
void multiplyTwoLinkedLists(struct Node* firstHead, struct Node* secondHead, struct Node** newLinkedListHead) {
int _1 = 0, _2 = 0;
while (firstHead || secondHead) {
if (firstHead) {
_1 = _1 * 10 + firstHead->data;
firstHead = firstHead->next;
}
if (secondHead) {
_2 = _2 * 10 + secondHead->data;
secondHead = secondHead->next;
}
}
int result = _1 * _2;
while (result) {
addNewNode(newLinkedListHead, result % 10);
result /= 10;
}
}
void printLinkedList(struct Node *node) {
while(node != NULL) {
cout << node->data << "->";
node = node->next;
}
cout << "NULL" << endl;
}
int main(void) {
struct Node* firstHead = NULL;
struct Node* secondHead = NULL;
addNewNode(&firstHead, 1);
addNewNode(&firstHead, 2);
addNewNode(&firstHead, 3);
printLinkedList(firstHead);
addNewNode(&secondHead, 1);
addNewNode(&secondHead, 2);
printLinkedList(secondHead);
struct Node* newLinkedListHead = NULL;
multiplyTwoLinkedLists(firstHead, secondHead, &newLinkedListHead);
printLinkedList(newLinkedListHead);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과를 확인할 수 있습니다.
3->2->1->NULL
2->1->NULL
6->7->4->1->NULL
동작 원리와 참고 사항
addNewNode 함수는 새 노드를 항상 리스트의 맨 앞에 삽입하므로, 노드를 추가한 순서와 실제 리스트에 저장되는 순서는 서로 반대가 됩니다. multiplyTwoLinkedLists 함수는 각 리스트를 순회하면서 _1 = _1 * 10 + 현재 자릿수 방식으로 정수를 조립하고, 두 수를 곱한 뒤 결과를 한 자릿수씩 잘라내어(% 10, /= 10) 새로운 연결 리스트를 구성합니다.
이 방식은 두 숫자가 int 범위(약 ±21억) 안에 들어올 때만 정확하게 동작합니다. 자릿수가 매우 많아 값이 오버플로될 가능성이 있다면, 문자열이나 배열 기반의 임의 정밀도 곱셈 기법을 사용해야 합니다. 시간 복잡도는 리스트의 길이를 n, m이라 할 때 O(n + m)으로 효율적입니다.