연결 리스트에서 교차 노드의 곱 구하기 (C 언어)

n개의 노드로 구성된 연결 리스트가 주어졌을 때, 교차로 배치된 노드들(홀수 번째 위치의 노드)의 값들을 모두 곱한 결과를 출력하는 것이 과제입니다. 이때 노드의 실제 위치를 변경하지 않고, 오직 교차 노드들의 곱만 계산하여 출력하면 됩니다.

문제 예시

입력 : 10 20 30 40 50 60
출력 : 15000

위 예시에서 첫 번째 노드인 10부터 시작하여 교차 노드는 10, 30, 50이 됩니다. 따라서 이들의 곱은 10 × 30 × 50 = 15000입니다.

그림으로 이해하기

아래 그림에서 첫 번째 노드부터 시작할 때 파란색 노드들이 계산에 포함되는 교차 노드이고, 빨간색 노드들은 계산에서 제외되는 노드입니다.

해결 접근 방식

• 노드 타입의 임시 포인터 temp를 선언합니다.
• head 포인터가 가리키는 첫 번째 노드를 temp에 대입합니다.
• (temp->next != NULL && temp != NULL && temp->next->next != NULL) 조건이 성립하는 동안 temp를 두 칸씩 앞으로 이동시킵니다.
• 이동할 때마다 product = product * (temp->data)로 곱을 누적합니다.

알고리즘 설계

시작
1단계 -> 노드 구조체와 temp, next, head 포인터 생성
    struct node
        int data
        struct node *next, *head, *temp
    종료
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
        ELSE
            temp = head
            WHILE temp->next != NULL
                temp = temp->next
            newnode->next = NULL
            temp->next = newnode
3단계 -> 리스트를 출력하는 함수 선언
    void display()
        IF head == NULL
            "노드 없음" 출력
        ELSE
            temp = head
            WHILE temp != NULL
                temp->data 출력
                temp = temp->next
4단계 -> 교차 노드의 곱을 찾는 함수 선언
    void alternate()
        int product 선언
        temp = head
        product = head->data
        WHILE (temp->next != NULL && temp != NULL && temp->next->next != NULL)
            temp = temp->next->next
            product = product * (temp->data)
        product 출력
5단계 -> main() 함수
    struct node* head = NULL로 리스트 생성
    insert(10) 등으로 노드 삽입
    display()로 리스트 출력
    alternate()로 교차 노드의 곱 계산
종료

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;
    if(head == NULL) {
        head = newnode;
        head->next = NULL;
    } else {
        temp=head;
        while(temp->next!=NULL) {
            temp=temp->next;
        }
        newnode->next=NULL;
        temp->next=newnode;
    }
}
//리스트를 출력하는 함수
void display() {
    if(head==NULL)
        printf("no node ");
    else {
        temp=head;
        while(temp!=NULL) {
            printf("%d ",temp->data);
            temp=temp->next;
        }
    }
}
//교차 노드의 곱을 구하는 함수
void alternate() {
    int product;
    temp=head;
    product=head->data;
    while(temp->next!=NULL && temp!=NULL && temp->next->next!=NULL) {
        temp=temp->next->next;
        product=product * (temp->data);
    }
    printf("\nproduct of alternate nodes is %d : " ,product);
}
int main() {
    //리스트 생성
    struct node* head = NULL;
    //리스트에 요소 삽입
    insert(10);
    insert(20);
    insert(30);
    insert(40);
    insert(50);
    insert(60);
    //리스트 출력
    printf("linked list is : ");
    display();

    //교차 노드의 곱을 구하는 함수 호출
    alternate();
    return 0;
}

실행 결과

linked list is : 10 20 30 40 50 60
product of alternate nodes is : 15000