연결 목록에 요소가 거의 없다고 가정해 보겠습니다. 마지막 n개 요소의 곱셈 결과를 찾아야 합니다. n의 값도 제공됩니다. 따라서 목록이 [5, 7, 3, 5, 6, 9]이고 n =3인 경우 결과는 5 * 6 * 9 =270이 됩니다.
과정은 간단합니다. 우리는 단순히 왼쪽에서 시작하여 현재 요소를 읽은 다음 요소를 스택에 추가합니다. 스택을 채운 후 n개의 요소를 제거하고 prod와 곱합니다. (초기 prod는 1), n개의 요소가 순회되면 중지합니다.
예시
#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