C++로 arr[i] ≥ arr[j]인 모든 배열 쌍의 최대 모듈로(나머지) 값 구하기

이 문제에서는 n개의 요소로 이루어진 배열이 주어지며, arr[i] >= arr[j]를 만족하는 모든 배열 쌍에 대해 최대 모듈로(나머지) 값을 찾는 프로그램을 작성하는 것이 목표입니다.

즉, arr[i] >= arr[j] 조건을 만족하는 쌍들 중에서 arr[i] % arr[j] 값이 가장 커지는 경우를 찾아야 합니다.

먼저 예제를 통해 문제를 자세히 살펴보겠습니다.

입력 − arr[] = {3, 5, 9}

출력 − 4

풀이 −

가능한 모든 쌍 (arr[i], arr[j])에 대한 나머지 값:
5, 3 => 5 % 3 = 2
9, 3 => 9 % 3 = 0
9, 5 => 9 % 5 = 4

이 문제를 해결하는 가장 단순한 방법은 두 개의 중첩 루프를 돌며 가능한 모든 쌍의 나머지를 계산한 뒤 그중 최댓값을 찾는 것입니다. 하지만 이 방법은 시간 복잡도가 O(n²)에 달하기 때문에 배열의 크기가 커지면 비효율적입니다.

훨씬 더 효율적인 접근 방식은 정렬된 배열을 활용하는 것입니다. 알고리즘은 다음과 같은 순서로 동작합니다.

배열의 각 요소 arr[j]에 대해, 배열 내 최댓값보다 커질 때까지 arr[j]의 배수인 값 x를 차례로 구합니다. 그다음 x 이하가 되는 배열의 값 arr[i]를 찾아 arr[i] % arr[j]를 계산하고, 매 연산마다 그 결과를 maxModulo 변수에 저장하면서 최댓값을 갱신합니다.

실제 예제를 통해 이 알고리즘이 어떻게 작동하는지 단계별로 확인해 보겠습니다.

arr = {3, 5, 9}
arr[j] = 3 (j = 0일 때),
x = {6, 9}
x = 6일 때, arr[i] = 5,
arr[i] % arr[j] = 5 % 3 = 2, maxModulo = 2
x = 9일 때, arr[i] = 9,
arr[i] % arr[j] = 9 % 3 = 0, maxModulo = 2
arr[j] = 5 (j = 1일 때),
x = {10}
x = 10일 때, arr[i] = 9,
arr[i] % arr[j] = 9 % 5 = 4, maxModulo = 4

이처럼 정렬과 배수 탐색을 활용하면 모든 쌍을 일일이 검사하지 않고도 최댓값을 빠르게 찾을 수 있어, 단순 이중 루프 방식보다 성능이 크게 향상됩니다.

예제 코드

arr[i] >= arr[j]를 만족하는 모든 배열 쌍의 최대 모듈로를 구하는 C++ 프로그램

#include <bits/stdc++.h>
using namespace std;
int maxModulo(int arr[], int n) {
    int maxModulo = 0;
    sort(arr, arr + n);
    for (int j = n - 2; j >= 0; --j) {
        if (maxModulo >= arr[j])
            break;
        if (arr[j] == arr[j + 1])
            continue;
        for (int k = 2 * arr[j]; k <= arr[n - 1] + arr[j]; k += arr[j]) {
            int i = lower_bound(arr, arr + n, k) - arr;
            maxModulo = max(maxModulo, arr[i - 1] % arr[j]);
        }
    }
    return maxModulo;
}
int main() {
    int arr[] = {3, 5, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"The maximum modulo of all pairs is "<<maxModulo(arr, n);
}

실행 결과

The maximum modulo of all pairs is 4