Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 단일 연결 리스트에서 최소 및 최대 소수 찾기

문제 개요

n개의 양의 정수로 이루어진 연결 리스트가 주어졌을 때, 리스트에 포함된 소수(prime number) 중에서 값이 가장 작은 소수와 가장 큰 소수를 찾아야 합니다.

예를 들어 다음과 같은 리스트가 주어진 경우를 살펴보겠습니다.

10 -> 4 -> 1 -> 12 -> 13 -> 7 -> 6 -> 2 -> 27 -> 33
이 경우 최소 소수는 2이고, 최대 소수는 13입니다.

여기서 10, 4, 1, 12, 6, 27, 33은 모두 소수가 아니므로 후보에서 제외되며, 남은 13, 7, 2 중에서 최솟값과 최댓값을 구하게 됩니다.

알고리즘

이 문제는 에라토스테네스의 체(Sieve of Eratosthenes)를 활용하면 효율적으로 해결할 수 있습니다. 전체 과정은 다음과 같습니다.

  1. 연결 리스트에 담긴 숫자들 중 최댓값을 구합니다. 이 값을 maxNumber라고 부릅니다.
  2. 1부터 maxNumber까지의 범위에서 소수 여부를 판별하는 불리언(Boolean) 배열을 생성합니다. 인덱스가 소수이면 true, 아니면 false가 저장됩니다.
  3. 연결 리스트를 처음부터 끝까지 순회하면서 각 노드의 값이 소수인지 배열을 통해 확인하고, 그중 최솟값과 최댓값을 갱신합니다.

소수 판별을 매번 반복 계산하는 대신 한 번의 체 생성으로 처리하기 때문에, 리스트의 길이가 길어져도 빠르게 동작한다는 장점이 있습니다.

예제 코드

다음은 위 알고리즘을 C++로 구현한 전체 코드입니다.

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <list>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;

void printMinAndMaxPrimes(list<int> intList) {
    // 리스트에서 최댓값을 구함
    int maxNumber = *max_element(intList.begin(), intList.end());

    // 에라토스테네스의 체로 소수 테이블 생성
    vector<bool> primes(maxNumber + 1, true);
    primes[0] = primes[1] = false;
    for (int p = 2; p * p <= maxNumber; ++p) {
        if (primes[p]) {
            for (int i = p * 2; i <= maxNumber; i += p) {
                primes[i] = false;
            }
        }
    }

    // 리스트를 순회하며 최소/최대 소수 찾기
    int minPrime = INT_MAX;
    int maxPrime = INT_MIN;
    for (auto it = intList.begin(); it != intList.end(); ++it) {
        if (primes[*it]) {
            minPrime = min(minPrime, *it);
            maxPrime = max(maxPrime, *it);
        }
    }

    cout << "Prime number of min value = " << minPrime << "\n";
    cout << "Prime number of max value = " << maxPrime << "\n";
}

int main() {
    int arr[] = {10, 4, 1, 12, 13, 7, 6, 2, 27, 33};
    list<int> intList(arr, arr + SIZE(arr));
    printMinAndMaxPrimes(intList);
    return 0;
}

코드 설명

  • 최댓값 탐색: STL의 max_element 함수를 사용해 리스트 전체에서 가장 큰 값을 한 번에 구합니다.
  • 소수 테이블 생성: vector<bool>을 모두 true로 초기화한 뒤, 0과 1은 소수가 아니므로 false로 설정합니다. 이후 2부터 시작해 제곱근까지만 확인하면서 해당 수의 배수들을 모두 지워 나갑니다.
  • 최종 순회: 초기값을 각각 INT_MAX와 INT_MIN으로 설정해 두면, 어떤 입력이 들어와도 안전하게 비교할 수 있습니다.

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.

Prime number of min value = 2
Prime number of max value = 13

시간 복잡도

에라토스테네스의 체 생성에는 O(N log log N)의 시간이 걸리고(N은 리스트 내 최댓값), 리스트 순회에는 O(n)의 시간이 걸립니다(n은 노드 개수). 따라서 전체 시간 복잡도는 O(N log log N)이며, 추가로 사용하는 공간은 소수 테이블을 위한 O(N)입니다.