문제 개요
숫자로 이루어진 배열이 주어졌을 때, 인덱스와 배열 요소의 곱을 비교하여 아래 조건을 만족하는 쌍(pair)의 개수를 찾는 것이 목표입니다.
만약 i * arr[i] > j * arr[j]라면, (arr[i], arr[j])는 유효한 쌍입니다.
예를 들어 배열이 [5, 4, 3, 2, 1]이라면, 조건을 만족하는 쌍은 [3, 1]과 [2, 1] 두 개입니다.
예제로 이해하기
예제 1
입력 − arr[] = [1, 5, 4, 1, 2, 8, 3]
출력 − i*arr[i] > j*arr[j] 조건을 만족하는 쌍의 개수: 3
설명 − 유효한 쌍은 (5, 1), (4, 1), (8, 3)입니다.
예제 2
입력 − arr[] = [-1, -2, 3, 4, 5, 6]
출력 − i*arr[i] > j*arr[j] 조건을 만족하는 쌍의 개수: 1
설명 − 유효한 쌍은 (-1, -2)입니다.
접근 방법
가장 직관적인 방법은 이중 반복문을 사용해 가능한 모든 쌍을 하나씩 확인하는 브루트 포스(Brute Force) 방식입니다. 바깥쪽 반복문으로 인덱스 i를 순회하고, 안쪽 반복문으로 i보다 뒤에 있는 인덱스 j를 순회하면서 매번 i*arr[i] > j*arr[j] 조건을 검사합니다. 조건이 참이면 카운트를 증가시키고, 모든 탐색이 끝난 후 카운트를 반환하면 됩니다.
정수형 배열과 그 크기를 준비합니다.
condition_pair() 함수는 배열과 배열의 크기를 매개변수로 받아 조건을 만족하는 쌍의 개수를 반환합니다.
카운트 변수를 0으로 초기화합니다.
바깥쪽 반복문으로 i를 0부터 size-2까지 순회합니다.
안쪽 반복문으로 j를 i+1부터 size-1까지 순회합니다.
(i * arr[i]) > (j * arr[j])가 참이면 카운트를 1 증가시킵니다.
모든 반복이 종료되면 count에는 조건을 만족하는 쌍의 총 개수가 저장됩니다.
count를 결과값으로 반환합니다.
C++ 구현 예제
#include <iostream>
using namespace std;
int condition_pair(int arr[], int size){
int count = 0;
for (int i = 0; i < size - 1; i++){
for (int j = i + 1; j < size; j++){
if(i*arr[i] > j*arr[j]){
count++;
}
}
}
return count;
}
int main(){
int arr[] = { 2, 4, 1, 9, 6 };
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"i*arr[i] > j*arr[j] 조건을 만족하는 쌍의 개수: "<<condition_pair(arr, size);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
i*arr[i] > j*arr[j] 조건을 만족하는 쌍의 개수: 2
시간 복잡도 및 성능 개선 팁
위 접근 방식은 두 개의 중첩 반복문을 사용하므로 시간 복잡도는 O(n²)입니다. 따라서 배열의 크기가 커지면 실행 시간이 빠르게 늘어납니다.
성능을 개선하려면 각 인덱스에 대해 val[k] = k * arr[k] 값을 미리 계산해 두면 좋습니다. 그러면 이 문제는 i < j이면서 val[i] > val[j]인 쌍, 즉 역전(inversion) 쌍을 세는 문제와 동일해집니다. 병합 정렬(Merge Sort)이나 펜윅 트리(BIT)를 활용하면 O(n log n) 시간 안에 해결할 수 있으므로, 입력 크기가 큰 경우에는 이러한 최적화 기법을 고려하는 것이 좋습니다.