문제 개요
서로 다른 정수들로 이루어진 배열이 주어졌을 때, 곱이 서로 같은 튜플(tuple)의 총 개수를 구하는 것이 목표입니다.
튜플 (a, b, c, d)가 a × b = c × d 조건을 만족하면 유효한 튜플로 간주합니다.
예시
입력:
arr[] = {2, 4, 6, 3}출력:
8
설명: 조건을 만족하는 튜플은 총 8개로, (2, 6, 3, 4), (2, 6, 4, 3), (6, 2, 3, 4), (6, 2, 4, 3), (3, 4, 2, 6), (4, 3, 2, 6), (3, 4, 6, 2), (4, 3, 6, 2)이며, 모두 a × b = c × d를 만족합니다.
해결 접근 방법
이 문제의 핵심 아이디어는 맵(map)을 활용해 배열 내 모든 쌍(pair)의 곱을 저장하는 것입니다.
곱을 키(key)로, 해당 곱이 등장한 빈도를 값(value)으로 저장하면 같은 곱을 만드는 쌍들을 손쉽게 그룹화할 수 있습니다.
모든 원소 쌍의 곱을 맵에 기록한 뒤, 맵을 순회하면서 (a × b = c × d) 형태로 같은 곱을 공유하는 쌍의 개수를 계산합니다.
특정 곱 값이 f번 등장했다면, 즉 같은 곱을 만드는 쌍이 f개라면 이 중 두 쌍을 고르는 방법은 f × (f−1) / 2가지입니다. 선택된 두 쌍의 네 숫자는 자리를 바꾸는 방식으로 최대 8가지 순열(permutation)을 만들 수 있으므로, 전체 튜플 수는 f × (f−1) / 2 × 8이 됩니다.
알고리즘 단계
배열 원소를 입력받습니다.
정수 함수 countTuple(int *arr, int n)은 배열과 그 크기를 입력으로 받아, (a × b = c × d) 형태로 같은 곱을 가지는 튜플의 개수를 반환합니다.
키는 쌍의 곱, 값은 해당 곱의 빈도인 맵을 생성합니다.
맵을 순회하며 같은 곱을 가지는 튜플의 수를 누적하여 계산합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int countTuple(int *arr, int n) {
map<int, int> mp;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
mp[arr[i] * arr[j]]++;
int ans = 0;
for (auto it : mp)
ans += (it.second * (it.second - 1) / 2) * 8;
return ans;
}
int main(){
int n=4;
int arr[n]= {2,4,6,3};
int res= countTuple(arr,n);
cout<<res<<" ";
return 0;
}실행 결과
8
위 코드를 실행하면 곱이 같은 튜플의 개수인 8이 출력됩니다. 시간 복잡도는 모든 쌍을 확인하는 데 O(n²), 맵 연산에 로그 계수가 추가되어 전체적으로 O(n² log n) 수준이며, 브루트 포스로 네 원소를 모두 탐색하는 O(n⁴)보다 훨씬 효율적입니다.