문제 개요
양의 정수로 이루어진 배열 arr[]가 주어졌을 때, 배열의 두 요소로 만들 수 있는 쌍 (A, B) 가운데 A가 등장하는 횟수(빈도)가 B 이상이고 동시에 B가 등장하는 횟수가 A 이상인 쌍의 개수를 구하는 것이 목표입니다.
예제를 통해 자세히 살펴보겠습니다.
입력 − int arr[] = { 3, 3, 3, 5, 5, 6, 6 }
출력 − 조건을 만족하는 쌍의 개수: 1
설명 − 이 배열에서 3은 정확히 3번 등장합니다. 따라서 쌍 (3, 3)은 "3이 3번 이상 등장한다"는 조건을 만족하는 유일한 유효한 쌍이며, 결과는 1이 됩니다.
입력 − int arr[] = { 3, 3, 3, 3, 3, 5, 5, 5, 6, 6 }
출력 − 조건을 만족하는 쌍의 개수: 3
설명 − 이 배열에서 3은 5번, 5는 3번 등장합니다. 따라서 (3, 3), (3, 5), (5, 3) 세 쌍이 모두 조건을 충족합니다. 예를 들어 쌍 (3, 5)에서 3은 5번 이상 등장하고 5는 3번 이상 등장하므로 유효합니다. 반면 6은 2번밖에 등장하지 않아 어떤 쌍에도 포함될 수 없습니다. 결과는 3입니다.
접근 방법
이 문제는 해시 기반 컨테이너인 unordered_map을 사용하면 효율적으로 해결할 수 있습니다. 먼저 배열 요소별 등장 횟수를 맵에 저장한 뒤, 맵을 순회하면서 각 값과 빈도의 조합이 조건을 만족하는지 확인하고, 만족할 때마다 쌍의 개수를 증가시킵니다.
정수 배열 arr[]를 입력으로 받습니다.
frequency_other_value(int arr[], int size) 함수는 배열과 크기를 인자로 받아, A가 적어도 B번 이상 등장하고 B 역시 적어도 A번 이상 등장하는 쌍 (A, B)의 개수를 반환합니다.
쌍의 개수를 세는 변수 count를 0으로 초기화합니다.
배열 요소와 그 빈도를 저장할 unordered_map<int, int> um을 선언하고, 배열을 한 번 순회하면서 채웁니다.
맵을 순회하면서 각 키 값을 start, 해당 빈도를 end로 놓고, 1부터 end까지의 값 j에 대해 um[j] >= start를 만족하는지 검사합니다.
조건을 만족할 때마다 count를 1씩 증가시킵니다.
모든 순회가 끝나면 count를 결과로 반환합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int frequency_other_value(int arr[], int len){
int count = 0;
unordered_map<int, int> um;
for (int i = 0; i < len; ++i){
um[arr[i]]++;
}
for (auto it : um){
int start = it.first;
int end = it.second;
for (int j = 1; j <= end; j++){
if (um[j] >= start){
count++;
}
}
}
return count;
}
int main(){
int arr[] = { 3, 3, 3, 5, 5, 6, 6};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of pairs in an array such that frequency of one is at least value of other are: "<<frequency_other_value(arr, size);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Count of pairs in an array such that frequency of one is at least value of other are: 1
주어진 배열에서 조건을 만족하는 쌍은 (3, 3) 하나뿐이므로 최종 결과값은 1입니다.