문제 소개
숫자로 구성된 배열 Arr[]가 주어졌을 때, 가능한 모든 쌍 중에서 최대 차이(maxdiff)와 같은 차이를 가지는 쌍의 개수를 세는 것이 목표입니다. 이때 쌍은 (i != j) 조건을 만족해야 하며, 두 원소의 차이가 배열 전체에서 가장 커야 합니다.
풀이 과정은 다음과 같습니다. 먼저 (i != j) 조건에서 만들 수 있는 최대 차이를 구하여 maxdiff에 저장한 뒤, 차이가 maxdiff와 일치하는 모든 쌍의 개수를 세면 됩니다.
예제를 통해 자세히 살펴보겠습니다.
예제 1
입력 − arr[] = { 1, 2, 3, 2, 4, 1, 5 }
출력 − 최대 차이를 가지는 쌍을 선택하는 방법의 수 − 2
설명 −
배열의 최솟값은 1, 최댓값은 5이므로 최대 차이 = 5 - 1 = 4 쌍 1 [ 1,2,3,2,4,1,5 ] → (1, 5) 차이 = 4 쌍 2 [ 1,2,3,2,4,1,5 ] → (1, 5) 차이 = 4 최대 차이를 가지는 쌍의 개수 = 2
예제 2
입력 − arr[] = { 2, 4, 2, 4 }
출력 − 최대 차이를 가지는 쌍을 선택하는 방법의 수 − 4
설명 −
배열의 최솟값은 2, 최댓값은 4이므로 최대 차이 = 4 - 2 = 2 쌍 1 [ 2,4,2,4 ] → (2, 4) 차이 = 2 쌍 2 [ 2,4,2,4 ] → (2, 4) 차이 = 2 쌍 3 [ 2,4,2,4 ] → (4, 2) 차이 = 2 쌍 4 [ 2,4,2,4 ] → (2, 4) 차이 = 2 최대 차이를 가지는 쌍의 개수 = 4
알고리즘 설계
아래 프로그램에 적용된 접근 방식은 다음과 같습니다.
- 임의의 정수로 초기화된 배열 Arr[]를 준비합니다.
- 배열의 길이를 저장할 변수 N을 선언합니다.
- countWays(int arr[], int n) 함수는 배열과 그 길이를 입력으로 받아, 최대 차이와 같은 차이를 가지는 쌍을 선택하는 방법의 수를 반환합니다.
- 방법의 수를 세기 위한 변수 count를 0으로 초기화합니다.
- 각 쌍의 차이를 저장할 변수 diff를 사용합니다.
- 모든 쌍 중 최대 차이를 저장할 변수 maxdiff를 사용합니다.
- 배열을 한 번 순회하며 최댓값과 최솟값을 찾아 각각 maxx와 mini에 저장합니다.
- maxdiff는 maxx - mini로 계산합니다. 배열에서 만들 수 있는 가장 큰 차이는 반드시 '최댓값 − 최솟값'이기 때문입니다.
- 두 개의 중첩 for 루프를 사용해 모든 쌍을 검사합니다. 외부 루프는 0 ≤ i < n-1, 내부 루프는 i < j < n 범위로 실행합니다.
- diff = arr[i] - arr[j]와 diff = arr[j] - arr[i]를 각각 계산하고, diff == maxdiff라면 count를 증가시킵니다. (순서가 다른 두 경우를 서로 다른 쌍으로 간주)
- 모든 루프가 종료되면 count에는 조건을 만족하는 쌍의 총 개수가 저장됩니다.
- count를 결과로 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int countWays(int arr[], int n){
int count = 0;
int diff;
int maxdiff = 0;
int mini, maxx;
mini = maxx = arr[0];
// 배열에서 최솟값과 최댓값 찾기
for (int i = 0; i < n; i++){
if(arr[i] < mini){
mini = arr[i];
}
if(arr[i] > maxx){
maxx = arr[i];
}
}
// 최대 차이 계산
maxdiff = maxx - mini;
// 모든 쌍을 검사하여 최대 차이와 일치하는 쌍의 개수 세기
for (int i = 0; i < n-1; i++){
for (int j = i+1; j < n; j++){
diff = arr[i] - arr[j]; // 쌍 1
if (diff == maxdiff){
count++;
}
diff = arr[j] - arr[i]; // 쌍 2
if (diff == maxdiff){
count++;
}
}
}
return count;
}
int main(){
int Arr[] = { 3, 2, 1, 1, 3 };
int N = 5; // 배열 길이
cout << endl << "최대 차이를 가지는 쌍을 선택하는 방법의 수 : " << countWays(Arr, N);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −
최대 차이를 가지는 쌍을 선택하는 방법의 수 : 4
시간 복잡도 및 개선 아이디어
위 알고리즘은 모든 쌍을 검사하므로 시간 복잡도는 O(n²)입니다. 배열의 크기가 커지면 비효율적일 수 있습니다.
다음과 같이 O(n)으로 개선할 수 있습니다.
- 배열을 한 번만 순회하여 최솟값(mini), 최댓값(maxx)을 구하고, 각 값의 등장 횟수를 셉니다.
- mini ≠ maxx인 경우, 정답은 (mini의 개수) × (maxx의 개수)입니다. 최대 차이를 만들려면 반드시 최솟값 하나와 최댓값 하나를 짝지어야 하기 때문입니다.
- 배열의 모든 원소가 동일한 값(mini == maxx)이라면, 가능한 모든 쌍의 개수는 n × (n-1) / 2입니다.