단일 연결 리스트(Singly Linked List) 노드의 곱 구하기

n개의 노드가 주어졌을 때, 단일 연결 리스트(singly linked list)에 담긴 모든 노드 값의 곱을 출력하는 것이 이번 문제의 목표입니다. 프로그램은 첫 번째 노드(헤드)부터 시작하여 NULL을 만날 때까지 리스트의 모든 노드를 순회하면서 곱을 누적해야 합니다.

예시

입력 : 1 2 3 4 5
출력 : 120

위 예제에서는 첫 번째 노드부터 시작해 1, 2, 3, 4, 5를 차례대로 순회하며 각 노드의 값을 곱합니다. 따라서 1 × 2 × 3 × 4 × 5 = 120이 최종 결과가 됩니다.

접근 방법

• node 타입의 임시 포인터 temp를 하나 선언합니다.
• temp가 헤드 포인터(head)가 가리키는 첫 번째 노드를 가리키도록 설정합니다.
• temp가 NULL이 아닌 동안 temp를 다음 노드(temp->next)로 계속 이동시킵니다.
• 노드를 지날 때마다 product = product * (temp->data) 연산으로 곱을 누적합니다.

알고리즘

Start
Step 1 -> 노드 구조체를 생성하고, temp·next·head를 구조체 노드를 가리키는 포인터로 선언
    struct node
        int data
        struct node *next, *head, *temp
    End
Step 2 -> 리스트에 노드를 삽입하는 함수 선언
    void insert(int val)
        struct node* newnode = (struct node*)malloc(sizeof(struct node))
        newnode->data = val
        IF head == NULL
            head = newnode
            head->next = NULL
        End
        Else
            temp = head
            Loop While temp->next != NULL
                temp = temp->next
            End
            newnode->next = NULL
            temp->next = newnode
        End
Step 3 -> 리스트를 출력하는 함수 선언
    void display()
        IF head == NULL
            Print "no node"
        Else
            temp = head
            Loop While temp != NULL
                Print temp->data
                temp = temp->next
            End
        End
Step 4 -> 모든 노드의 곱을 구하는 함수 선언
    void product_nodes()
        int product = 1
        temp = head
        Loop While temp != NULL
            product = product * (temp->data)
            temp = temp->next
        End
        Print product
Step 5 -> main() 함수에서
    insert() 함수를 호출해 리스트에 노드 삽입
    display() 함수를 호출해 리스트 출력
    product_nodes() 함수를 호출해 노드의 곱 계산
Stop

C 언어 구현 예제

#include<stdio.h>
#include<stdlib.h>
// 노드 구조체 정의
struct node{
    int data;
    struct node *next;
}*head,*temp;

// 리스트에 노드를 삽입하는 함수
void insert(int val){
    struct node* newnode = (struct node*)malloc(sizeof(struct node));
    newnode->data = val;
    newnode->next = NULL;
    if(head == NULL){
        head = newnode;
        temp = head;
    } else {
        temp->next = newnode;
        temp = temp->next;
    }
}

// 리스트를 화면에 출력하는 함수
void display(){
    if(head == NULL)
        printf("no node ");
    else{
        temp = head;
        while(temp != NULL){
            printf("%d ", temp->data);
            temp = temp->next;
        }
    }
}

// 모든 노드의 곱을 구하는 함수
void product_nodes(){
    int product = 1;
    temp = head;
    while(temp != NULL){
        product = product * (temp->data);
        temp = temp->next;
    }
    printf("\nproduct of nodes is : %d", product);
}

int main(){
    // 리스트에 요소 삽입
    insert(1);
    insert(2);
    insert(3);
    insert(4);
    insert(5);
    insert(6);

    // 리스트 출력
    printf("linked list is : ");
    display();

    // 노드 곱 계산 함수 호출
    product_nodes();
    return 0;
}

위 코드에서 head와 temp는 전역 변수로 선언되어 있으므로 main() 안에서 head를 별도로 초기화할 필요가 없습니다. 전역 포인터는 프로그램 시작 시 자동으로 NULL로 초기화되기 때문입니다.

출력 결과

linked list is : 1 2 3 4 5 6
product of nodes is : 720

복잡도 분석

이 알고리즘은 리스트의 각 노드를 정확히 한 번씩만 방문하므로 시간 복잡도는 O(n)입니다. 또한 곱을 저장하는 변수 외에 추가적인 메모리를 사용하지 않기 때문에 공간 복잡도는 O(1)입니다.