C++로 연결 리스트의 마지막 N개 노드 곱 구하기

연결 리스트(Linked List)에 여러 개의 요소가 저장되어 있을 때, 마지막 n개 노드 값의 곱을 구하는 문제를 생각해 볼 수 있습니다. 여기서 n값은 미리 주어집니다.

예를 들어 연결 리스트가 [5, 7, 3, 5, 6, 9]이고 n = 3이라면, 마지막 세 개의 요소는 5, 6, 9이므로 결과는 5 × 6 × 9 = 270이 됩니다.

문제 해결 접근 방식

풀이 과정은 매우 간단합니다. 핵심 아이디어는 다음과 같습니다.

알고리즘 단계

1. 연결 리스트를 왼쪽(머리)부터 순회하면서 각 노드의 값을 스택(Stack)에 차례대로 push합니다.
2. 모든 요소를 스택에 넣었다면, 스택의 top에서부터 n개의 요소를 pop하면서 결과값(prod)에 곱해 나갑니다. 초기 prod 값은 1입니다.
3. n개의 요소를 모두 처리하면 순회를 멈추고 최종 곱을 반환합니다.

스택은 LIFO(Last In, First Out) 구조이기 때문에, 연결 리스트를 역방향으로 탐색하지 않고도 마지막 요소부터 꺼낼 수 있다는 점이 이 방법의 장점입니다.

C++ 구현 예제

#include<iostream>
#include<stack>
using namespace std;

class Node {
public:
    int data;
    Node *next;
};

Node* getNode(int data) {
    Node *newNode = new Node;
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

void append(struct Node** start, int key) {
    Node* new_node = getNode(key);
    Node *p = (*start);
    if(p == NULL){
        (*start) = new_node;
        return;
    }
    while(p->next != NULL){
        p = p->next;
    }
    p->next = new_node;
}

long long prodLastNElements(Node *start, int n) {
    if(n <= 0)
        return 0;
    stack<int> stk;
    long long res = 1;
    Node* temp = start;
    while (temp != NULL) {
        stk.push(temp->data);
        temp = temp->next;
    }
    while(n--){
        res *= stk.top();
        stk.pop();
    }
    return res;
}

int main() {
    Node *start = NULL;
    int arr[] = {5, 7, 3, 5, 6, 9};
    int size = sizeof(arr)/sizeof(arr[0]);
    int n = 3;
    for(int i = 0; i<size; i++){
        append(&start, arr[i]);
    }
    cout << "Product of last n elements: " << prodLastNElements(start, n);
}

실행 결과

Product of last n elements: 270

코드 설명

prodLastNElements 함수는 먼저 n이 0 이하인 경우 0을 반환하여 잘못된 입력을 처리합니다. 이후 연결 리스트 전체를 순회하며 모든 값을 스택에 저장한 뒤, 스택에서 n개의 값을 pop하면서 곱을 계산합니다.

곱셈 결과가 커질 수 있으므로 결과 변수는 long long 타입으로 선언하여 오버플로우를 방지했습니다. 시간 복잡도는 리스트를 한 번 순회하고 스택에서 n개를 꺼내므로 O(N), 공간 복잡도는 스택에 모든 요소를 저장하므로 O(N)입니다.