문제 설명
양의 정수로 이루어진 두 배열 X와 Y가 주어집니다. x는 배열 X의 원소, y는 배열 Y의 원소일 때, xy > yx를 만족하는 쌍(x, y)의 개수를 구하는 것이 이 글의 목표입니다.
예를 들어 X = [2, 1, 6], Y = [1, 5]라고 가정해 보겠습니다. 이 경우 조건을 만족하는 쌍은 (2, 1), (2, 5), (6, 1)로 총 3개이므로 결과값은 3이 됩니다.
핵심 아이디어
모든 쌍을 하나씩 검사하는 브루트 포스 방식은 O(m×n)의 시간이 걸려 비효율적입니다. 대신 다음과 같은 수학적 성질을 활용하면 문제를 훨씬 효율적으로 해결할 수 있습니다.
"몇 가지 예외를 제외하면, y > x일 때 항상 xy > yx가 성립한다."
이 성질을 이용하면 매 쌍마다 거듭제곱을 직접 계산할 필요 없이, "Y 배열에서 x보다 큰 값이 몇 개 있는지"만 세면 됩니다.
알고리즘 단계
- 배열 Y를 오름차순으로 정렬합니다.
- X의 각 원소 x에 대해, Y에서 x보다 큰 값 중 가장 작은 값의 인덱스를 찾습니다. 이때 이진 탐색(binary search)을 사용하거나, C++ STL의
upper_bound()함수를 활용할 수 있습니다. - 찾은 인덱스 이후의 모든 원소는 x보다 크므로 조건을 만족합니다. 해당 개수를 정답에 더합니다.
예외 처리
위 규칙에는 몇 가지 예외가 있으므로 반드시 처리해야 합니다.
- x = 0인 경우: 0y = 0이고 y0 = 1이므로 조건을 만족하는 쌍이 없습니다. 0을 반환합니다.
- x = 1인 경우: 1y = 1 > y1 = y가 되려면 y = 0뿐입니다. 따라서 Y에서 0의 개수를 반환합니다.
- x = 2인 경우: 23 = 8 < 32 = 9이고, 24 = 16 = 42이므로 y = 3, 4는 제외해야 합니다. Y에서 3과 4의 개수를 빼줍니다.
- x = 3인 경우: 32 = 9 > 23 = 8이므로 y = 2도 조건을 만족합니다. Y에서 2의 개수를 더해줍니다.
- x ≥ 2인 경우: y = 0 또는 y = 1이면 항상 조건을 만족하므로(예: 21 = 2 > 12 = 1), Y에서 0과 1의 개수를 추가로 더해줍니다.
C++ 구현 예제
#include <iostream>
#include <algorithm>
using namespace std;
int count(int x, int Y[], int n, int no_of_y[]) {
if (x == 0)
return 0;
if (x == 1)
return no_of_y[0];
int* index = upper_bound(Y, Y + n, x);
int ans = (Y + n) - index;
ans += (no_of_y[0] + no_of_y[1]);
if (x == 2)
ans -= (no_of_y[3] + no_of_y[4]);
if (x == 3)
ans += no_of_y[2];
return ans;
}
int howManyPairs(int X[], int Y[], int m, int n) {
int no_of_y[5] = {0};
for (int i = 0; i < n; i++)
if (Y[i] < 5)
no_of_y[Y[i]]++;
sort(Y, Y + n);
int total_pairs = 0;
for (int i=0; i< m; i++)
total_pairs += count(X[i], Y, n, no_of_y);
return total_pairs;
}
int main() {
int X[] = {2, 1, 6};
int Y[] = {1, 5};
int m = sizeof(X)/sizeof(X[0]);
int n = sizeof(Y)/sizeof(Y[0]);
cout << "Total pair count: " << howManyPairs(X, Y, m, n);
}
실행 결과
Total pair count: 3
시간 복잡도
배열 Y를 정렬하는 데 O(n log n), 각 x에 대해 이진 탐색을 수행하는 데 O(log n)이 걸리므로, 전체 시간 복잡도는 O((m + n) log n)입니다. 모든 쌍을 직접 비교하는 O(m×n) 방식에 비해 훨씬 효율적입니다.