이 문제에서는 하나의 연결 리스트(Linked List)가 주어집니다. 우리의 과제는 연결 리스트를 순회하면서 짝수 값을 가진 노드들의 합과 홀수 값을 가진 노드들의 합을 각각 구하는 것입니다.
문제 이해를 위한 예시
입력 : 연결 리스트 : 3 -> 2 -> 5 -> 7 -> 1 -> 9
출력 : evenSum = 2 ; oddSum = 25
설명 −
evenSum = 2
oddSum = 3 + 5 + 7 + 1 + 9 = 25
위 예시에서 짝수 값은 2뿐이므로 evenSum은 2가 되고, 나머지 홀수 값들을 모두 더하면 oddSum은 25가 됩니다.
해결 접근 방식
이 문제를 푸는 가장 간단한 방법은 연결 리스트를 처음부터 끝까지 한 번 순회하면서, 각 노드의 값이 짝수인지 홀수인지 판별한 뒤 그 값을 각각의 합계 변수(evenSum 또는 oddSum)에 더해주는 것입니다.
리스트를 한 번만 순회하면 되므로 시간 복잡도는 O(n)으로 매우 효율적이며, 추가로 사용하는 공간도 합계 변수 두 개뿐이므로 공간 복잡도는 O(1)입니다.
알고리즘
1단계 − 연결 리스트를 순회합니다.
1.1단계 − 현재 노드의 값이 짝수라면 evenSum에 더합니다.
1.2단계 − 현재 노드의 값이 홀수라면 oddSum에 더합니다.
2단계 − 순회가 끝나면 evenSum과 oddSum을 출력하거나 반환합니다.
구현 코드
다음은 위에서 설명한 해결 방법의 동작을 보여주는 C++ 프로그램입니다.
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
// 리스트 끝에 새 노드를 삽입하는 함수
void insertNode(Node** root, int item) {
Node *ptr = *root, *temp = new Node;
temp->data = item;
temp->next = NULL;
if (*root == NULL)
*root = temp;
else {
while (ptr->next != NULL)
ptr = ptr->next;
ptr->next = temp;
}
}
// 짝수 여부를 판별하는 함수
bool isEven(int a){
return (a % 2 == 0);
}
// 짝수 노드의 합과 홀수 노드의 합을 계산하는 함수
void findEvenAndOddSum(Node* root) {
int oddSum = 0, evenSum = 0;
Node* node = root;
while (node != NULL) {
if (isEven(node->data))
evenSum += node->data;
else
oddSum += node->data;
node = node->next;
}
cout << "짝수 값 노드의 합은 " << evenSum << endl;
cout << "홀수 값 노드의 합은 " << oddSum;
}
int main() {
Node* root = NULL;
insertNode(&root, 3);
insertNode(&root, 2);
insertNode(&root, 5);
insertNode(&root, 7);
insertNode(&root, 1);
insertNode(&root, 9);
insertNode(&root, 6);
findEvenAndOddSum(root);
return 0;
}
실행 결과
짝수 값 노드의 합은 8
홀수 값 노드의 합은 25
위 프로그램에서 입력된 리스트는 3 -> 2 -> 5 -> 7 -> 1 -> 9 -> 6 입니다. 짝수 값인 2와 6을 더한 evenSum은 8이 되고, 홀수 값인 3, 5, 7, 1, 9를 모두 더한 oddSum은 25가 됩니다.
참고: 짝수 판별 함수는
a % 2 == 0조건을 사용해야 올바르게 동작합니다. 나머지 연산 결과가 0일 때만 짝수이므로, 이 조건을 반대로 작성하면 짝수와 홀수의 합이 서로 뒤바뀌어 출력될 수 있으니 주의해야 합니다.