이 문제에서는 하나의 연결 리스트(Linked List)가 주어지며, 우리가 해야 할 작업은 연결 리스트의 교대(홀수 번째) 노드들의 값 합계를 출력하는 것입니다.
연결 리스트란?
연결 리스트는 각 데이터 요소가 링크(pointer)를 통해 서로 연결된 선형 자료구조입니다. 배열과 달리 메모리상에 연속적으로 저장되지 않으며, 각 노드는 데이터와 다음 노드를 가리키는 포인터로 구성됩니다.
문제 이해하기
이제 본격적으로 문제를 살펴보겠습니다. 여기서는 연결 리스트의 교대 노드, 즉 인덱스 0, 2, 4, 6, ... 위치에 있는 노드들의 값을 더해야 합니다.
예시
입력:
4 → 12 → 10 → 76 → 9 → 26 → 1
출력:
24
설명:
교대 노드만 선택하여 더하면 — 4 + 10 + 9 + 1 = 24
접근 방법
이 문제를 해결하려면 연결 리스트의 각 노드를 순서대로 방문하면서, 해당 노드가 교대 위치에 있을 때만 값을 합계에 더하면 됩니다. 현재 노드를 더할 차례인지 아닌지를 판단하기 위해 플래그(flag) 변수를 활용합니다.
구현 방식은 크게 두 가지로 나눌 수 있습니다.
- 반복문(Iteration) 기반 접근 — while 루프를 사용하여 노드를 순회합니다.
- 재귀(Recursion) 기반 접근 — 함수 호출을 통해 다음 노드로 넘어가며 처리합니다.
방법 1: 반복문을 사용한 풀이
반복문 방식에서는 플래그 변수를 두고, 노드를 하나씩 이동할 때마다 플래그를 뒤집어(true ↔ false) 교대 노드만 더합니다.
코드 예시
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node* next;
};
void pushNode(struct Node** head_ref, int newData) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = newData;
newNode->next = (*head_ref);
(*head_ref) = newNode;
}
int sumAlternateNodeIt(struct Node* head) {
bool flag = true;
int sum = 0;
while (head != NULL){
if (flag)
sum += head->data;
flag = !flag;
head = head->next;
}
return sum;
}
int main(){
struct Node* head = NULL;
pushNode(&head, 54);
pushNode(&head, 12);
pushNode(&head, 87);
pushNode(&head, 1);
pushNode(&head, 99);
pushNode(&head, 11);
cout<<"The sum of alternate nodes is "<<sumAlternateNodeIt(head);
return 0;
}출력 결과
The sum of alternate nodes is 24
동작 원리: 위 코드에서는 노드 삽입 시 head 앞쪽에 새 노드를 추가하므로, 실제 리스트는 11 → 99 → 1 → 87 → 12 → 54 순서가 됩니다. 따라서 교대 노드인 11 + 1 + 12 = 24가 합계로 계산됩니다.
방법 2: 재귀를 사용한 풀이
재귀 방식에서는 현재 노드의 처리가 끝나면 자기 자신을 호출하여 다음 노드로 이동하고, 호출할 때마다 플래그 값을 반전시켜 전달합니다.
코드 예시
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node* next;
};
void pushNode(struct Node** head_ref, int new_data){
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
void sumAlternateNodeRec(struct Node* node, int& sum, bool flag = true){
if (node == NULL)
return;
if (flag == true)
sum += (node->data);
sumAlternateNodeRec(node->next, sum, !flag);
}
int main(){
struct Node* head = NULL;
pushNode(&head, 54);
pushNode(&head, 12);
pushNode(&head, 87);
pushNode(&head, 1);
pushNode(&head, 99);
pushNode(&head, 11);
int sum = 0;
sumAlternateNodeRec(head, sum, true);
cout<<"The sum of alternate nodes is "<<sum;
return 0;
}출력 결과
The sum of alternate nodes is 24
동작 원리: 재귀 함수는 노드가 NULL일 때 종료됩니다. 플래그가 true인 경우에만 현재 노드의 데이터를 참조로 전달된 sum 변수에 더하고, 다음 노드로 재귀 호출할 때는 플래그를 반전(!flag)시켜 교대 노드만 누적되도록 합니다.
정리
두 방식 모두 시간 복잡도는 O(n)으로 동일하지만, 반복문 방식은 추가 메모리 없이 처리되는 반면, 재귀 방식은 호출 스택에 O(n)의 공간이 필요하다는 차이가 있습니다. 리스트가 매우 길다면 반복문 방식이 스택 오버플로우 위험 없이 안전하게 사용할 수 있는 선택입니다.