C++로 각 배열 요소의 나머지가 모두 같아지는 수 k 찾기

이 튜토리얼에서는 각 배열 요소를 나눴을 때 나머지가 모두 같아지는 수 k를 찾는 프로그램을 C++로 작성해 보겠습니다. 먼저 예시를 통해 문제를 이해해 봅시다.

입력 − arr = {10, 4, 2}

출력 − 1 2

핵심 원리

두 수 x, y(x > y)가 있고 두 수의 차이를 x − y = d라고 가정해 보겠습니다. 그러면 x = y + d로 표현할 수 있습니다.

여기서 x % k = y % k를 만족하는 수 k가 존재한다고 해봅시다. 이 조건을 이용해 양변에 k에 대한 나머지 연산을 적용하고 d의 값을 유도해 보겠습니다.

x % k = (y + d) % k
y % k = y % k + d % k
d % k = 0

위 계산에서 알 수 있듯이, 수 k가 x와 y의 차이(d)의 약수라면, x와 y를 k로 나눈 나머지는 반드시 서로 같게 됩니다. 즉, k는 두 수의 차이의 약수여야 한다는 것이 핵심입니다.

이 원리를 배열의 모든 요소에 확장 적용하면 문제를 해결할 수 있습니다. 문제 해결 단계를 살펴보겠습니다.

알고리즘 접근 방법

숫자들로 배열을 초기화합니다.
여기서 d는 배열 요소 중 최댓값과 최솟값의 차이입니다.
sort 함수를 사용해 배열을 오름차순으로 정렬합니다.
마지막 요소와 첫 번째 요소의 차이를 구합니다.
만약 차이가 0이라면 배열의 모든 요소가 같다는 의미이므로, 어떤 수로 나누더라도 나머지가 동일합니다. 따라서 가능한 k의 개수는 무한합니다.
차이가 0이 아니라면 d의 모든 약수를 구해 저장합니다.
각 약수를 후보 k로 삼아, 배열의 모든 요소를 해당 값으로 나눴을 때 나머지가 일치하는지 확인하고 조건을 만족하는 값들을 출력합니다.

예제 코드

전체 코드를 살펴보겠습니다.

#include <bits/stdc++.h>
using namespace std;

void findNumbers(int arr[], int n) {
    sort(arr, arr + n);
    int d = arr[n - 1] - arr[0];
    // 모든 요소가 같은지 확인
    if (d == 0) {
        cout << "Infinite number of k's";
        return;
    }
    // d의 약수 구하기
    vector<int> v;
    for (int i = 1; i * i <= d; i++) {
        if (d % i == 0) {
            v.push_back(i);
            if (i != d / i) {
                v.push_back(d / i);
            }
        }
    }
    // 조건을 만족하는 k 찾기
    for (int i = 0; i < v.size(); i++) {
        int temp = arr[0] % v[i];
        int j;
        for (j = 1; j < n; j++) {
            if (arr[j] % v[i] != temp) {
                break;
            }
        }
        if (j == n)
            cout << v[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {10, 4, 2};
    findNumbers(arr, 3);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.

1 2

배열 {10, 4, 2}의 경우 최댓값 10과 최솟값 2의 차이는 8이며, 8의 약수인 1, 2, 4, 8 중에서 실제로 모든 요소의 나머지를 일치시키는 값은 1과 2입니다.

결론

이번 튜토리얼에서는 배열의 모든 요소를 나눈 나머지가 동일해지는 수 k를 찾는 방법을 배웠습니다. 최댓값과 최솟값의 차이를 구한 뒤 그 약수들을 검증하는 방식으로 효율적으로 문제를 해결할 수 있습니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.