C++로 배열을 '좋은 배열'로 만들기 위해 제거해야 할 최소 요소 개수 구하기

문제 설명

배열 "arr"이 주어졌을 때, 이 배열을 좋은(good) 배열로 만들기 위해 제거해야 하는 최소 요소 개수를 구하는 것이 과제입니다.

여기서 좋은 배열이란, 수열 a₁, a₂, a₃ … aₙ의 모든 원소 a[i]에 대해 i ≠ j인 다른 원소 a[j]가 존재하여 a[i] + a[j]가 2의 거듭제곱이 되는 경우를 말합니다.

예시

arr1[] = {1, 1, 7, 1, 5}

위 배열에서 원소 '5'를 하나만 삭제하면 배열은 좋은 배열이 됩니다. 삭제 후에는 어떤 쌍을 골라도 arr[i] + arr[j]가 2의 거듭제곱이 됩니다.

• arr[0] + arr[1] = (1 + 1) = 2 → 2의 거듭제곱
• arr[0] + arr[2] = (1 + 7) = 8 → 2의 거듭제곱

알고리즘

1. a[i] + a[j]가 2의 거듭제곱이 되는 짝 a[j]를 가질 수 없는 a[i]만 삭제하면 됩니다.
2. 각 값이 배열에 몇 번 등장하는지 빈도를 계산합니다.
3. a[i]와 짝이 될 수 있는 a[j]가 존재하지 않는지 확인합니다.

핵심 아이디어는 해시 맵(빈도 맵)을 활용하는 것입니다. 먼저 배열의 모든 원소 빈도를 기록한 뒤, 각 원소 a[i]에 대해 2⁰부터 2³⁰까지의 거듭제곱 값을 순회하며 pair = 2ʲ − a[i]가 맵에 존재하는지 검사합니다. 이때 pair == a[i], 즉 자기 자신과 짝이 되는 경우에는 해당 값이 두 번 이상 등장해야만 유효한 짝으로 인정됩니다.

C++ 구현 예제

#include <iostream>
#include <map>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int minDeleteRequred(int *arr, int n){
    map<int, int> frequency;
    for (int i = 0; i < n; ++i) {
        frequency[arr[i]]++;
    }
    int delCnt = 0;
    for (int i = 0; i < n; ++i) {
        bool doNotRemove = false;
        for (int j = 0; j < 31; ++j) {
            int pair = (1 << j) - arr[i];
            if (frequency.count(pair) &&
                (frequency[pair] > 1 ||
                (frequency[pair] == 1 &&
                pair != arr[i]))) {
                doNotRemove = true;
                break;
            }
        }
        if (!doNotRemove) {
            ++delCnt;
        }
    }
    return delCnt;
}
int main(){
    int arr[] = {1, 1, 7, 1, 5};
    cout << "삭제해야 할 최소 요소 개수 = " << minDeleteRequred(arr, SIZE(arr)) << endl;
    return 0;
}

출력 결과

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

삭제해야 할 최소 요소 개수 = 1

복잡도 분석

빈도 맵을 구성하는 데 O(n log n)의 시간이 걸리고, 각 원소마다 최대 31개의 거듭제곱 후보를 확인하므로 전체 시간 복잡도는 O(31 · n log n)입니다. 공간 복잡도는 서로 다른 원소의 개수에 비례하여 최대 O(n)입니다.