문제 개요
단일 연결 리스트(singly linked list)가 주어졌을 때, 노드에 저장된 값이 소수(prime)인 모든 노드를 찾아 그 곱을 계산해 출력하는 것이 이번 글의 목표입니다. 예를 들어 리스트가 10 → 2 → 7 → 6 → 85로 구성되어 있다면, 소수에 해당하는 값은 2와 7뿐이므로 최종 결과는 2 × 7 = 14가 됩니다.
입력 · 출력 예시
입력:
10 2 7 6 85
출력:
14
설명: 리스트를 처음부터 끝까지 순회하면서 각 노드의 데이터가 소수인지 검사합니다. 10은 소수가 아니므로 건너뛰고, 2와 7은 소수이므로 곱에 포함되며, 6과 85 역시 소수가 아니므로 제외됩니다.
곱: 2 × 7 = 14
접근 방법
- 노드 타입의 임시 포인터(예: temp)를 하나 선언합니다.
- 임시 포인터를 head 포인터가 가리키는 첫 번째 노드로 설정합니다.
- 포인터를 한 노드씩 앞으로 이동하며 현재 노드의 데이터가 소수인지 확인합니다.
- 소수라면 product = product × (현재 노드의 데이터)로 갱신합니다.
- 소수가 아니라면 별도 처리 없이 다음 노드로 이동합니다.
- 리스트 끝까지 순회를 마친 뒤 product 변수의 최종 값을 출력합니다.
알고리즘
Start
Step 1 → 리스트에 삽입할 노드 구조체 생성
struct node
int data;
node* next
End
Step 2 → 노드를 리스트에 삽입하는 함수 선언
void push(node** head_ref, int data)
node* newnode = (node*)malloc(sizeof(struct node))
newnode→data = data
newnode→next = (*head_ref)
(*head_ref) = newnode
End
Step 3 → 소수 판별 함수 선언
bool isPrime(int data)
IF data <= 1
return false
IF data <= 3
return true
IF data % 2 == 0 || data % 3 == 0
return false
FOR int i = 5; i * i <= data; i = i + 6
IF data % i == 0 || data % (i + 2) == 0
return false
return true
Step 4 → 곱을 계산하는 함수 선언
void product(node* head_ref)
int product = 1
node* ptr = head_ref
WHILE ptr != NULL
IF isPrime(ptr→data)
product *= ptr→data
ptr = ptr→next
Print product
Step 5 → main()
node* head = NULL 선언
push(&head, 10), push(&head, 2), push(&head, 7),
push(&head, 6), push(&head, 85) 호출
product(head) 호출
Stop
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
// 노드 구조체 정의
struct node {
int data;
node* next;
};
// 노드를 리스트 맨 앞에 삽입하는 함수
void push(node** head_ref, int data) {
node* newnode = (node*)malloc(sizeof(struct node));
newnode->data = data;
newnode->next = (*head_ref);
(*head_ref) = newnode;
}
// 소수 판별 함수
bool isPrime(int data) {
if (data <= 1)
return false;
if (data <= 3)
return true;
if (data % 2 == 0 || data % 3 == 0)
return false;
for (int i = 5; i * i <= data; i = i + 6)
if (data % i == 0 || data % (i + 2) == 0)
return false;
return true;
}
// 소수 노드들의 곱을 구하는 함수
void product(node* head_ref) {
int product = 1;
node* ptr = head_ref;
while (ptr != NULL) {
if (isPrime(ptr->data)) {
product *= ptr->data;
}
ptr = ptr->next;
}
cout << "연결 리스트의 모든 소수 노드의 곱 = " << product;
}
int main() {
node* head = NULL;
push(&head, 10);
push(&head, 2);
push(&head, 7);
push(&head, 6);
push(&head, 85);
product(head);
return 0;
}
실행 결과
위 코드를 컴파일하여 실행하면 다음과 같은 결과가 출력됩니다.
연결 리스트의 모든 소수 노드의 곱 = 14
코드 동작 원리
push() 함수는 새 노드를 항상 리스트의 맨 앞에 추가하므로, 10, 2, 7, 6, 85 순서로 호출하면 실제 리스트는 85 → 6 → 7 → 2 → 10 순서로 구성됩니다. product() 함수는 head부터 마지막 노드까지 한 번씩 순회하면서 isPrime()으로 각 노드의 값을 검사하고, 소수인 경우에만 곱에 누적합니다. 이 예제에서 소수에 해당하는 값은 7과 2이므로 최종 결과는 7 × 2 = 14가 됩니다.
복잡도 분석
- 시간 복잡도: 리스트를 한 번 순회하는 데 O(n), 각 노드 값에 대한 소수 판별에 최대 O(√m)이 소요되므로 전체 시간 복잡도는 O(n·√m)입니다. (n은 노드 개수, m은 노드 값의 최댓값)
- 공간 복잡도: 별도의 추가 메모리를 사용하지 않으므로 O(1)입니다.