양의 정수로 이루어진 배열이 주어졌을 때, LCM(arr[i], arr[j]) > min(arr[i], arr[j]) 조건을 만족하는 원소 쌍의 개수를 구하는 것이 목표입니다. 즉, 한 쌍을 이루는 두 원소의 최소공배수(LCM)가 두 원소 중 작은 값보다 커야 한다는 의미입니다.
참고: 쌍 (arr[i], arr[j])과 (arr[j], arr[i])는 같은 쌍이므로 중복해서 세어서는 안 됩니다.
예제로 이해하기
예제 1
입력 − arr[] = [1, 5, 4, 2]
출력 − 조건을 만족하는 쌍의 개수: 6
설명 − 다음 6개의 쌍이 모두 조건을 만족합니다.
쌍 1 (1, 5): LCM = 5 > 1 쌍 2 (1, 4): LCM = 4 > 1 쌍 3 (1, 2): LCM = 2 > 1 쌍 4 (5, 4): LCM = 20 > 4 쌍 5 (5, 2): LCM = 10 > 2 쌍 6 (4, 2): LCM = 4 > 2
예제 2
입력 − arr[] = [3, 3, 6]
출력 − 조건을 만족하는 쌍의 개수: 2
설명 − (3, 6) 쌍 두 개만 조건을 만족합니다. 값이 같은 (3, 3) 쌍은 LCM이 3으로 min인 3과 같아 조건을 만족하지 않습니다.
쌍 1 (3, 6): LCM = 6 > 3 쌍 2 (3, 6): LCM = 6 > 3
핵심 아이디어와 접근 방식
서로 다른 두 양의 정수 a, b(a ≠ b)에 대해 최소공배수 LCM(a, b)는 항상 max(a, b) 이상이므로 min(a, b)보다 반드시 큽니다. 반면 두 수가 같으면 LCM(a, a) = a가 되어 min과 같아지므로 조건을 만족하지 못합니다.
따라서 조건이 거짓이 되는 유일한 경우는 두 원소의 값이 같은 경우입니다. 이 성질을 활용하면 복잡한 LCM 연산 없이도 문제를 간단히 풀 수 있습니다.
- 전체 원소로 만들 수 있는 모든 쌍의 개수를 구합니다. (size × (size − 1) / 2)
- 같은 값끼리 이루는 쌍의 개수를 구해 빼줍니다. 어떤 값이 freq번 등장한다면 그 값으로 만들 수 있는 쌍은 freq × (freq − 1) / 2개입니다.
알고리즘 단계
- 정수 배열과 그 크기를 입력받습니다.
- conditional_pair(int arr[], int size) 함수는 조건을 만족하는 쌍의 개수를 반환합니다.
- count를 0으로 초기화합니다.
- unordered_map<int, int> um을 선언하여 각 원소의 빈도수를 기록합니다.
- 맵을 순회하며 각 빈도수 temp에 대해 temp × (temp − 1) / 2를 count에 누적합니다. 이는 같은 값으로 만들 수 있는 모든 쌍의 개수입니다.
- 전체 가능한 쌍의 개수를 size × (size − 1) / 2로 계산합니다.
- 전체 쌍 개수에서 같은 값의 쌍 개수를 뺀 결과를 반환합니다.
C++ 코드 구현
#include <bits/stdc++.h>
using namespace std;
// 조건 LCM(arr[i], arr[j]) > min(arr[i], arr[j])을 만족하는 쌍의 개수를 반환
int conditional_pair(int arr[], int size){
int count = 0;
// 각 원소의 빈도수를 저장할 해시 맵
unordered_map<int, int> um;
for (int i = 0; i < size; i++){
um[arr[i]]++;
}
// 같은 값끼리 이루는 쌍의 개수 계산
for (auto it : um){
int temp = it.second;
count += temp * (temp - 1) / 2;
}
// 전체 쌍 개수에서 같은 값의 쌍 개수를 뺌
int total = (size * (size - 1)) / 2;
return total - count;
}
int main(){
int arr[] = { 4, 1, 7, 3, 2 };
int size = sizeof(arr) / sizeof(arr[0]);
cout << "LCM(arr[i], arr[j]) > min(arr[i], arr[j])를 만족하는 쌍의 개수: "
<< conditional_pair(arr, size);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
LCM(arr[i], arr[j]) > min(arr[i], arr[j])를 만족하는 쌍의 개수: 10
복잡도 분석
시간 복잡도: O(n) — 배열을 한 번 순회해 빈도수를 계산하고, 맵을 한 번 순회합니다.
공간 복잡도: O(n) — 고유한 원소의 개수만큼 해시 맵 공간이 필요합니다.