C++로 배열에서 모든 요소를 나눌 수 있는 요소 찾기

개요

여러 개의 요소를 가진 배열 A가 있다고 가정해 봅시다. 이때 배열 A에 속한 요소 중에서 나머지 모든 요소를 나눌 수 있는(즉, 모든 요소가 해당 값으로 나누어 떨어지는) 값을 찾아야 합니다.

예를 들어 배열이 [15, 21, 69, 33, 3, 72, 81]과 같다면, 모든 숫자가 3으로 나누어 떨어지므로 정답은 3이 됩니다.

접근 방법

이 문제는 다음과 같은 간단한 아이디어로 해결할 수 있습니다.

1. 배열 A에서 가장 작은 수를 찾습니다. 어떤 수가 다른 모든 수를 나눌 수 있다면, 그 수는 반드시 최솟값의 약수여야 하기 때문입니다.
2. 배열의 모든 요소가 이 최솟값으로 나누어 떨어지는지 확인합니다.
3. 나누어 떨어진다면 그 최솟값을 반환하고, 하나라도 나누어 떨어지지 않으면 -1을 반환합니다.

C++ 구현 예제

#include<iostream>
#include<algorithm>
using namespace std;

int getNumber(int a[], int n) {
    int minNumber = *min_element(a, a+n);
    for (int i = 0; i < n; i++)
        if (a[i] % minNumber)
            return -1;
    return minNumber;
}

int main() {
    int a[] = { 15, 21, 69, 33, 3, 72, 81 };
    int n = sizeof(a) / sizeof(int);
    cout << "The number is: " << getNumber(a, n);
}

실행 결과

The number is: 3

코드 설명

• min_element(a, a+n): C++ 표준 라이브러리(<algorithm>)의 함수로, 배열에서 최솟값을 가리키는 반복자를 반환합니다. 역참조(*)를 통해 실제 최솟값을 얻습니다.
• a[i] % minNumber: 나머지 연산을 통해 각 요소가 최솟값으로 나누어 떨어지는지 검사합니다. 나머지가 0이 아니면 조건식이 참이 되어 즉시 -1을 반환합니다.

시간 복잡도

최솟값을 찾는 데 O(n), 전체 요소를 검사하는 데 O(n)이 소요되므로, 총 시간 복잡도는 O(n)입니다. 공간 복잡도는 추가 메모리를 사용하지 않으므로 O(1)입니다.