C++로 연결 리스트에 저장된 두 숫자를 곱하여 새로운 리스트 만들기

숫자들이 저장된 두 개의 연결 리스트(Linked List)가 주어졌을 때, 각 리스트가 나타내는 수를 곱한 결과를 세 번째 연결 리스트에 저장하는 방법을 알아보겠습니다. 이 문제는 각 연결 리스트에서 숫자를 추출해 실제 정수 값을 만든 뒤 곱셈을 수행하면 비교적 쉽게 해결할 수 있습니다.

문제 예시

입력

1 -> 2 -> NULL
2 -> 3 -> NULL

출력

2 -> 7 -> 6 -> NULL

위 예시에서 첫 번째 리스트는 12를, 두 번째 리스트는 23을 나타냅니다. 두 수를 곱하면 276이 되며, 이 결과가 세 번째 리스트에 저장됩니다.

알고리즘

두 개의 연결 리스트를 초기화합니다.
각 리스트의 숫자를 저장할 변수 두 개를 0으로 초기화합니다.
두 연결 리스트를 순회하면서 각 자릿수를 해당 변수 끝에 추가합니다. 즉, 기존 값에 10을 곱한 후 현재 노드의 데이터를 더하는 방식입니다.
완성된 두 숫자를 곱하여 결과를 변수에 저장합니다.
곱셈 결과의 각 자릿수를 추출해 새로운 연결 리스트를 생성합니다.
새로 만들어진 리스트를 출력합니다.

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 함수는 새 노드를 리스트의 맨 앞에 추가합니다. 따라서 main 함수에서 1, 2, 3 순서로 삽입하면 실제 리스트는 3→2→1 순으로 출력됩니다. multiplyTwoLinkedLists 함수는 두 리스트를 동시에 순회하면서 각 숫자를 누적하고(_1 = _1 * 10 + data), 완성된 두 수를 곱한 뒤 결과값의 마지막 자릿수부터 차례대로 새 리스트에 추가합니다. 맨 앞 삽입 방식 덕분에 최종 리스트는 올바른 자릿수 순서로 저장됩니다.

이 방식의 시간 복잡도는 O(n + m)입니다. 여기서 n과 m은 각 연결 리스트의 길이입니다. 단, 리스트가 매우 길어져 곱셈 결과가 int 범위를 초과할 경우 오버플로우가 발생할 수 있으므로, 큰 수를 다룰 때는 long long 타입 사용이나 문자열 기반 곱셈 방식을 고려하는 것이 좋습니다.