문제 소개
양의 정수로 이루어진 배열이 주어졌을 때, 배열 arr[]의 요소들 중에서 다음 조건을 만족하는 쌍(p, q)의 개수를 구하는 것이 목표입니다.
조건: p가 배열에서 최소 q번 이상 등장하고, 동시에 q가 배열에서 최소 p번 이상 등장해야 합니다.
구체적인 예제를 통해 살펴보겠습니다.
예제 1
입력 − int arr[] = { 3, 3, 3, 5, 5, 6, 6 }
출력 − 조건을 만족하는 쌍의 개수: 1
설명 − 숫자 3이 배열에서 정확히 3번 등장하므로 (3, 3)이 유효한 쌍이 됩니다. 다른 숫자들은 조건을 만족하지 않으므로, 유효한 쌍은 하나뿐이며 결과값은 1입니다.
예제 2
입력 − int arr[] = { 3, 3, 3, 3, 3, 5, 5, 5, 6, 6 }
출력 − 조건을 만족하는 쌍의 개수: 3
설명 − 이 경우 3이 5번 등장하고 5가 3번 등장하므로 (3, 3), (5, 5), (3, 5) 세 가지 쌍이 모두 유효합니다. 따라서 결과값은 3입니다.
알고리즘 접근 방식
정수 요소로 이루어진 배열을 입력받고, 배열의 크기를 계산한 후 이후 처리를 위해 함수에 전달합니다.
p와 q의 등장 횟수를 저장할 임시 변수 count를 선언합니다.
vector 타입의 변수 vec과 unordered_map 타입의 변수 um을 생성합니다.
0부터 배열 크기까지 FOR 루프를 실행합니다.
루프 내부에서 um[arr[i]] 값을 증가시키고, 해당 값이 1이라면(처음 등장하는 원소라면) vec에 arr[i]를 push_back 합니다.
0부터 vec의 크기까지 또 다른 FOR 루프를 실행하며, um[vec[i]] < vec[i]이면 continue로 건너뛰고, 값이 같으면 count를 1 증가시킵니다. 값이 더 큰 경우에는 count를 1 증가시킨 후, j를 vec[i] + 1부터 um[vec[i]]까지 반복하는 내부 루프를 시작합니다.
내부 j 루프에서 um[j] >= vec[i]인지 확인하고, 조건을 만족하면 count를 1 증가시킵니다.
모든 연산이 끝나면 count를 반환합니다.
최종 결과를 출력합니다.
구현 예제 코드
#include <bits/stdc++.h>
using namespace std;
int pair_count(int arr[], int len){
int count = 0;
vector<int> vec;
unordered_map<int, int> um;
for (int i = 0; i < len; i++){
um[arr[i]]++;
if (um[arr[i]] == 1){
vec.push_back(arr[i]);
}
}
for (int i = 0; i < vec.size(); i++){
if (um[vec[i]] < vec[i]){
continue;
}
else if (um[vec[i]] == vec[i]){
count++;;
}
else{
count++;
for (int j = vec[i] + 1; j <= um[vec[i]]; j++){
if (um[j] >= vec[i]){
count++;
}
}
}
}
return count;
}
int main(){
int arr[] = { 1, 1, 1, 5, 5, 1};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"p가 최소 q번, q가 최소 p번 등장하는 쌍의 개수: "<<pair_count(arr, size);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력 결과를 얻을 수 있습니다.
p가 최소 q번, q가 최소 p번 등장하는 쌍의 개수: 1
정리
이 알고리즘은 unordered_map을 활용해 각 숫자의 빈도를 O(n) 시간에 계산하고, 고유한 숫자들에 대해서만 조건을 검사함으로써 효율성을 높였습니다. 특히 빈도수가 숫자 자신보다 크거나 같은 경우에만 추가 탐색을 수행하므로, 불필요한 비교 연산을 크게 줄일 수 있다는 점이 핵심 최적화 포인트입니다.