C++로 정확히 K개의 부분 배열을 삭제하여 소수만 남긴 배열의 크기 최대화하기

문제 개요

N개의 양의 정수로 구성된 배열 Arr[]가 주어졌을 때, 정확히 K개의 부분 배열(연속된 구간)을 삭제하여 남은 원소들이 모두 소수가 되도록 만들고, 그 상태에서 남은 배열의 크기를 최대화하는 것이 이 문제의 목표입니다.

입력 예시 1

Arr[]={4, 3, 3, 4, 3, 4, 3}, K=2

출력

설명 − K=2이므로 정확히 2개의 부분 배열만 삭제할 수 있습니다.

Arr[0]과 Arr[3…5]를 삭제하면 Arr[]={3, 3, 3}이 남게 되며, 모든 원소가 소수이면서 가능한 최대 크기를 가집니다.

입력 예시 2

Arr[]={7, 6, 2, 11, 8, 3, 12}, K=2

출력

설명 − Arr[1]과 Arr[4…6]을 삭제하면 소수로만 이루어진 배열 Arr[]={7, 2, 11}이 남습니다.

풀이 접근 방법

먼저 에라토스테네스의 체를 sieve() 함수로 구현하여 호출하고, 모든 소수 여부를 prime[] 배열에 저장합니다.
MaxSize() 함수에서 i=0부터 i<N까지 반복하면서 합성수의 인덱스를 int형 벡터 vect에 저장합니다.
이어서 i=1부터 vect.size()까지 반복하며, 연속된 두 합성수 사이에 존재하는 소수의 개수를 계산해 int형 벡터 diff에 저장합니다.
sort() 함수를 사용해 diff 벡터를 오름차순으로 정렬합니다.
i=1부터 diff.size()까지 반복하며 diff 벡터의 누적 합(prefix sum)을 계산합니다. 이를 통해 삭제 시 함께 제거되어야 할 소수의 개수를 빠르게 알 수 있습니다.
if 문으로 불가능한 경우, 즉 K=0인데도 합성수가 존재하는 상황을 먼저 검사합니다.
K가 합성수의 개수보다 크거나 같다면, 모든 합성수와 일부 추가 소수까지 삭제하게 됩니다. 이때 각 삭제 구간의 길이를 1로 유지하는 것이 최적의 답을 얻는 방법입니다.
K가 합성수의 개수보다 작다면, 합성수를 포함한 부분 배열을 삭제해야 하며, 순수하게 소수로만 이루어진 구간은 삭제 대상에서 제외해야 합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
const int Num = 1e5;
bool prime[Num];
// 에라토스테네스의 체
void sieve(){
    for (int i = 2; i < Num; i++) {
        if (!prime[i]){
            for (int j = i + i; j < Num; j += i){
                prime[j] = 1;
            }
        }
    }
    prime[1] = 1;
}
int MaxSize(int* arr, int N, int K){
    vector<int> vect, diff;
    // 합성수의 인덱스를 벡터에 삽입
    for (int i = 0; i < N; i++){
        if (prime[arr[i]])
            vect.push_back(i);
    }
    /* 연속된 두 합성수 사이에 있는
    소수의 개수를 계산 */
    for (int i = 1; i < vect.size(); i++){
        diff.push_back(vect[i] - vect[i - 1] - 1);
    }
    // diff 벡터 정렬
    sort(diff.begin(), diff.end());
    // diff 벡터의 누적 합 계산
    for (int i = 1; i < diff.size(); i++){
        diff[i] += diff[i - 1];
    }
    // 불가능한 경우
    if (K > N || (K == 0 && vect.size())){
        return -1;
    }
    // 길이 1의 부분 배열 삭제
    else if (vect.size() <= K){
        return (N - K);
    }
    /* 부분 배열 삭제 시 함께
    제거되는 소수의 개수 계산 */
    else if (vect.size() > K){
        int tt = vect.size() - K;
        int sum = 0;
        sum += diff[tt - 1];
        int res = N - (vect.size() + sum);
        return res;
    }
}
// 메인 함수
int main(){
    sieve();
    int arr[] = { 7, 2, 3, 4, 3, 6, 3, 3 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int K = 2;
    cout<< MaxSize(arr, N, K);
    return 0;
}

출력

위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다 −