이 문제에서는 n개의 원소로 이루어진 배열이 주어지며, 주어진 배열에서 arr[i] % arr[j]의 최댓값을 찾는 프로그램을 작성해야 합니다.
쉽게 말해, 배열의 두 원소를 나누었을 때 나올 수 있는 나머지 중 가장 큰 값을 구하는 것이 목표입니다.
문제 이해를 위한 예시
입력: array[] = {3, 6, 9, 2, 1}
출력: 6
설명:
3%3 = 0; 3%6 = 3; 3%9 = 3; 3%2 = 1; 3%1 = 0
6%3 = 0; 6%6 = 0; 6%9 = 6; 6%2 = 0; 6%1 = 0
9%3 = 0; 9%6 = 3; 9%9 = 0; 9%2 = 1; 9%1 = 0
2%3 = 2; 2%6 = 2; 2%9 = 2; 2%2 = 0; 2%1 = 0
1%3 = 1; 1%6 = 1; 1%9 = 1; 1%2 = 1; 1%1 = 0
위의 모든 나머지 값 중 최댓값은 6입니다.
접근 방법
1. 완전 탐색 (비효율적)
가장 직관적인 방법은 배열의 모든 쌍 (i, j)에 대해 나머지를 일일이 계산한 뒤 그중 최댓값을 찾는 것입니다. 하지만 이 방법은 가능한 모든 조합을 검사해야 하므로 시간 복잡도가 O(n²)에 달해, 배열의 크기가 커지면 매우 비효율적입니다.
2. 정렬을 활용한 효율적인 방법
나눗셈의 기본 성질을 활용하면 훨씬 효율적으로 해결할 수 있습니다. 피제수 x보다 제수 y가 클 때(x < y) 나머지는 항상 x 자신이 됩니다. 따라서 배열에서 가장 큰 원소와 두 번째로 큰 원소만 고려하면 충분합니다.
배열을 오름차순으로 정렬하면 arr[n-1]이 최댓값, arr[n-2]가 두 번째 최댓값이 됩니다. 이때 arr[n-2] % arr[n-1] = arr[n-2]이며, 어떤 원소 조합도 arr[n-2]보다 큰 나머지를 만들 수 없으므로 정답은 곧 arr[n-2]입니다. 단, 배열의 모든 원소가 서로 같은 경우에는 어떤 나눗셈의 나머지도 0이 되므로 0을 반환해야 한다는 점에 유의해야 합니다.
구현 예제
위에서 설명한 해결 방법을 구현한 프로그램입니다.
#include <bits/stdc++.h>
using namespace std;
int maxRemainder(int arr[], int n){
bool hasSameValues = true;
for(int i = 1; i<n; i++) {
if (arr[i] != arr[i - 1]) {
hasSameValues = false;
break;
}
}
if (hasSameValues)
return 0;
sort(arr, arr+n);
return arr[n-2];
}
int main(){
int arr[] = { 3, 6, 9, 2, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"배열의 두 원소를 나눈 나머지의 최댓값: "<<maxRemainder(arr, n);
return 0;
}
출력
배열의 두 원소를 나눈 나머지의 최댓값: 6
복잡도 분석
배열 정렬에 O(n log n)의 시간이 소요되고, 모든 원소가 같은지 검사하는 과정은 O(n)이므로 전체 시간 복잡도는 O(n log n)입니다. 이는 완전 탐색 방식의 O(n²)보다 훨씬 효율적이며, 배열의 크기가 커져도 안정적인 성능을 보장합니다.