C++로 연결 리스트의 처음 k개 노드 곱 구하는 방법

연결 리스트의 처음 k개 노드 곱이란?

연결 리스트(Linked List)에 여러 개의 요소가 저장되어 있을 때, 처음 k개 요소의 곱을 구하는 문제를 생각해 보겠습니다. 예를 들어 연결 리스트가 [5, 7, 3, 5, 6, 9]이고 k = 3이라면, 결과는 5 × 7 × 3 = 105가 됩니다.

알고리즘 접근 방식

풀이 과정은 매우 간단합니다.

• 결괏값을 저장할 변수 prod를 1로 초기화합니다.
• 리스트의 왼쪽(머리 노드)부터 현재 노드의 값을 읽어 prod에 곱합니다.
• k개의 요소를 모두 순회하면 반복을 종료하고 결과를 반환합니다.

이 알고리즘의 시간 복잡도는 O(k)이며, 공간 복잡도는 O(1)입니다. 즉, 리스트 전체를 탐색할 필요 없이 앞부분 k개만 확인하면 되므로 매우 효율적입니다.

C++ 구현 예제

#include<iostream>
#include<cmath>
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 prodFirstKElements(Node *start, int k) {
    long long res = 1;
    int count = 0;
    Node* temp = start;
    while (temp != NULL && count != k) {
        res *= temp->data;
        count++;
        temp = temp->next;
    }
    return res;
}

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

실행 결과

Product of first k elements: 105

코드 설명

Node 클래스는 정수형 데이터(data)와 다음 노드를 가리키는 포인터(next)를 가지는 기본적인 연결 리스트 노드 구조체입니다. getNode() 함수는 새 노드를 생성하고 초기화하며, append() 함수는 리스트 끝에 새 요소를 추가합니다.

핵심 함수인 prodFirstKElements()는 res를 1로 초기화한 뒤, 머리 노드부터 시작하여 각 노드의 데이터를 res에 곱하고 count를 증가시킵니다. temp가 NULL이 되거나 count가 k에 도달하면 루프가 종료됩니다.

여기서 주목할 점은 결괏값 변수를 long long 타입으로 선언했다는 것입니다. 곱셈은 값이 빠르게 커질 수 있으므로, int 범위를 초과하는 오버플로우를 방지하기 위해 더 넓은 자료형을 사용하는 것이 안전합니다.