문제 이해하기
정수 배열 arr[]와 두 개의 수 A, B가 주어졌을 때, A와 B가 동일한 횟수만큼 등장하는 모든 부분 배열(subarray)의 개수를 구하는 것이 목표입니다.
예를 들어 배열이 [1,2,3]이고 A=1, B=2라고 하면, 조건을 만족하는 부분 배열은 [3], [1,2], [1,2,3]입니다.
예제
예제 1
입력 − arr[] = { 2, 2, 1, 1, 1, 5 }, A=1, B=5
출력 − 두 요소의 등장 횟수가 같은 부분 배열의 개수 − 4
설명 − 조건을 만족하는 부분 배열은 [2], [2], [2,2], [1,5]입니다. 앞의 세 개는 1과 5가 0회 등장하고, 마지막 하나는 두 요소가 각각 1회씩 등장합니다.
예제 2
입력 − arr[] = { 5,3,7,5,3 }, A=1, B=2
출력 − 두 요소의 등장 횟수가 같은 부분 배열의 개수 − 15
설명 − 1과 2가 한 번도 등장하지 않는(0회) 부분 배열들입니다.
[5], [3], [7], [5], [3] - 5
[5,3], [3,7], [7,5], [5,3] - 4
[5,3,7], [3,7,5], [7,5,3] - 3
[5,3,7,5], [3,7,5,3] - 2
[5,3,7,5,3] - 1
즉, 1과 2가 모두 0회 등장하는 부분 배열은 총 15개입니다.
접근 방법
두 개의 for 루프를 사용하여 가능한 모든 부분 배열을 생성합니다. 바깥 루프는 i=0부터 i<=size-1까지, 안쪽 루프는 j=i부터 j<=size-1까지 반복하며, 생성되는 부분 배열은 arr[i]부터 arr[j]까지의 범위입니다. 각 부분 배열에서 A와 B의 등장 빈도를 계산한 뒤, 두 값이 같으면 카운트를 증가시킵니다.
숫자 배열 arr[]를 준비합니다.
함수 sub_EqualOccurrence(int arr[], int size, int A, int B)는 배열을 받아 A와 B의 등장 횟수가 같은 부분 배열의 개수를 반환합니다.
초기 count 값을 0으로 설정합니다.
i=0부터 i<=size-1까지, 그리고 j=i부터 j<=size-1까지 두 개의 for 루프로 배열을 순회합니다.
부분 배열 arr[i]~arr[j]에 포함된 A와 B의 개수를 저장할 변수 total_A, total_B를 0으로 초기화합니다.
arr[j]가 A 또는 B와 일치하면 해당 변수(total_A 또는 total_B)를 증가시킵니다.
total_A == total_B이면 count를 증가시킵니다. (해당 부분 배열에는 A와 B가 같은 개수로 포함되어 있습니다.)
모든 반복이 끝나면 count를 결과로 반환합니다.
이 접근법은 모든 부분 배열을 직접 확인하므로 시간 복잡도는 O(n²)입니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int sub_EqualOccurrence(int arr[], int size, int A, int B){
int count = 0;
for (int i = 0; i <= size - 1; i++){
int total_A = 0;
int total_B = 0;
for (int j = i; j <= size - 1; j++){
if (arr[j] == A){
total_A++;
}
else if (arr[j] == B){
total_B++;
}
if(total_A == total_B){
count++;
}
}
}
return count;
}
// Driver code
int main(){
int arr[] = { 2, 3, 1, 1, 4, 5 };
int size = sizeof(arr) / sizeof(arr[0]);
int A = 1, B = 5;
cout<<"Count of subarrays with equal number of occurrences of two given elements are: "<<sub_EqualOccurrence(arr, size, A, B);
return (0);
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −
Count of subarrays with equal number of occurrences of two given elements are: 5