C++ 연결 리스트에서 각 노드의 작은 값 요소 합 구하기

이 문제에서는 두 개의 정수 값과 포인터로 구성된 노드를 가진 연결 리스트(Linked List)가 주어집니다. 우리의 과제는 각 노드에 포함된 두 값 중 더 작은 값들을 모두 찾아 그 합을 계산하는 프로그램을 만드는 것입니다.

연결 리스트의 각 노드에는 X와 Y라는 두 개의 요소가 있습니다. 프로그램은 각 노드를 순회하면서 min(X, Y), 즉 두 값 중 최솟값을 구하고, 이 최솟값들을 모두 더한 결과를 반환해야 합니다.

문제 예시

입력 −

(5,2)->(7,9)->(6,3)->(36,24)->(19,26)->null

출력 −

55

설명 −

각 노드에서 X와 Y 중 더 작은 값을 선택하면 다음과 같습니다.

node1 - 최솟값 = 5
node2 - 최솟값 = 7
node3 - 최솟값 = 3
node4 - 최솟값 = 24
node5 - 최솟값 = 19
합계 = 55

해결 접근 방법

이 문제는 매우 직관적인 방법으로 해결할 수 있습니다. 연결 리스트의 처음부터 끝까지 순회하면서 각 노드마다 X와 Y 중 최솟값을 구하고, 이를 합계 변수(sum)에 누적합니다. 리스트의 마지막 노드까지 처리가 완료되면 누적된 합계를 반환하면 됩니다.

알고리즘

초기화 − sum = 0

1단계 − 리스트를 순회하며 다음 작업을 수행합니다.

1.1단계 − head->X와 head->Y 중 최솟값을 구합니다.

1.2단계 − 구한 최솟값을 sum에 더합니다.

2단계 − 순회가 끝나면 sum을 반환합니다.

구현 예제

위 알고리즘의 동작을 보여주는 C++ 프로그램입니다.

#include <iostream>
using namespace std;
struct Node {
    int X;
    int Y;
    Node* next;
};
void addNode(Node** head, int x, int y){
    Node* ptr = *head;
    Node* temp = new Node();
    temp->X = x;
    temp->Y = y;
    temp->next = NULL;
    if (*head == NULL)
        *head = temp;
    else {
        while (ptr->next != NULL)
            ptr = ptr->next;
        ptr->next = temp;
    }
}
int findMinSum(Node* head){
    int sum = 0;
    while (head != NULL) {
        sum += min(head->X , head->Y);
        head = head->next;
    }
    return sum;
}
int main(){
    Node* head = NULL;
    addNode(&head, 5, 2);
    addNode(&head, 7, 9);
    addNode(&head, 6, 3);
    addNode(&head, 36, 24);
    addNode(&head, 19, 26);
    cout<<"연결 리스트 노드들의 작은 값 요소의 합은 "<<findMinSum(head)<<endl;
    return 0;
}

출력 결과

연결 리스트 노드들의 작은 값 요소의 합은 55

이 알고리즘의 시간 복잡도는 O(n)입니다. 여기서 n은 연결 리스트의 노드 개수이며, 리스트 전체를 한 번만 순회하면 되기 때문에 효율적인 해결 방법입니다.