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

C++로 중앙값이 부분 집합 자체에 포함되는 부분 집합의 개수 구하기

양수로만 이루어진 배열 arr[]가 주어졌을 때, 부분 집합을 구성하는 값들의 중앙값(median)이 그 부분 집합 자체에도 포함되어 있는 경우의 수를 모두 세는 것이 이 문제의 목표입니다.

예시로 이해하기

입력

arr[] = { 1,2,3 }

출력

중앙값이 동일한 부분 집합 안에 존재하는 부분 집합의 개수: 4

설명

중앙값이 집합 자체에 포함된 부분 집합은 다음과 같습니다.
[ 1 ]     → 중앙값 1
[ 2 ]     → 중앙값 2
[ 3 ]     → 중앙값 3
[ 1,2,3 ] → 중앙값 2

입력

arr[] = { 4,6,5 }

출력

중앙값이 동일한 부분 집합 안에 존재하는 부분 집합의 개수: 4

설명

[ 4 ], [ 6 ], [ 5 ], [ 4,6,5 ]

풀이 접근 방식

이 접근법에서는 부분 집합의 크기가 홀수인 경우와 짝수인 경우로 나누어 생각합니다. 원소 개수가 홀수인 부분 집합은 가운데 원소 자체가 곧 중앙값이 되므로 항상 조건을 만족합니다. 따라서 홀수 길이 부분 집합의 총 개수인 2n−1을 먼저 답에 더해 줍니다.

반면 원소 개수가 짝수인 부분 집합은 두 개의 가운데 원소가 서로 같은 값일 때만 중앙값이 집합 안에 존재하게 됩니다. 따라서 정렬된 배열에서 값이 같은 두 원소 쌍을 찾고, 그 쌍의 왼쪽과 오른쪽에서 나머지 원소를 고르는 조합의 수를 더해 주면 됩니다.

  • 양수로 이루어진 배열 arr[]를 입력으로 받습니다.
  • 함수 median_subset(arr, size)는 배열과 크기를 인자로 받아, 중앙값이 같은 부분 집합 안에 존재하는 부분 집합의 개수를 반환합니다.
  • 함수 check(int temp)는 정수 하나를 받아, i=2부터 i≤temp까지 반복하는 for 루프로 팩토리얼을 계산해 반환합니다.
  • 루프 안에서 count = count * i를 누적하고, 루프가 끝나면 그 값을 팩토리얼로 반환합니다.
  • 함수 com(int n, int r)은 n과 r을 받아 조합 nCr의 값을 반환합니다. 내부에서 temp = check(r) * check(n − r)을 계산한 뒤, temp_2 = check(n) / temp를 구해 반환합니다.
  • 함수 power(int n, int r)은 n과 r을 받아 nr의 값을 반환합니다.
  • r이 0이면 답은 1이므로 1을 반환합니다.
  • total = power(n, r / 2), 즉 nr/2를 먼저 구합니다.
  • total을 total2 % mod로 갱신합니다. 여기서 mod = 1000000007입니다.
  • r이 홀수이면 (total * n) % mod를, 짝수이면 total을 반환합니다.
  • median_subset() 함수 안에서는 count = power(2, size − 1)로 초기화합니다. 이 값은 홀수 길이 부분 집합의 총 개수입니다.
  • sort(arr, arr + size)로 배열을 오름차순 정렬합니다.
  • while 루프를 돌며 각 원소에 대해 바로 다음 원소부터 값이 같은 동안(두 가운데 원소 후보) 검사를 진행합니다.
  • temp_2 = size − 1 − temp로, 오른쪽 가운데 원소 기준 오른편에 남은 원소의 개수를 구합니다.
  • temp_3 = i로, 왼쪽 가운데 원소 기준 왼편에 있는 원소의 개수를 구합니다.
  • 짝수 길이 부분 집합의 경우의 수를 count에 더합니다. count = (count + com(temp_3 + temp_2, temp_3)) % mod
  • while 루프가 모두 끝나면 count가 최종 답이 됩니다.
  • count를 결과로 반환합니다.

예제 코드

#include <algorithm>
#include <iostream>
using namespace std;
#define mod 1000000007
int check(int temp){
    int count = 1;
    for (int i = 2; i <= temp; i++){
        count = count * i;
    }
    return count;
}
int com(int n, int r){
    int temp = check(r) * check(n - r);
    int temp_2 = check(n) / temp;
    return temp_2;
}
int power(int n, int r){
    if (r == 0){
        return 1;
    }
    int total = power(n, r / 2);
    total = (total * total) % mod;
    if (r % 2){
        int temp = (total * n) % mod;
        return temp;
    } else {
        return total;
    }
}
int median_subset(int* arr, int size){
    int count = power(2, size - 1);
    sort(arr, arr + size);
    for (int i = 0; i < size; ++i){
        int temp = i + 1;
        while (temp < size && arr[temp] == arr[i]){
            int temp_2 = size - 1 - temp;
            int temp_3 = i;
            count = (count + com(temp_3 + temp_2, temp_3)) % mod;
            temp++;
        }
    }
    return count;
}
int main(){
    int arr[] = { 4, 5, 4, 6 };
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"Count of number of subsets whose median is also present in the same subset are: "<<median_subset(arr, size);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

Count of number of subsets whose median is also present in the same subset are: 9

결과 분석

배열 { 4, 5, 4, 6 }을 정렬하면 { 4, 4, 5, 6 }이 됩니다. 홀수 길이 부분 집합은 2³ = 8개로 모두 조건을 만족하고, 짝수 길이 부분 집합 중에서는 가운데 두 원소가 같은 { 4, 4 } 한 가지만 추가로 가능합니다. 따라서 전체 답은 8 + 1 = 9가 됩니다.