C++에서 K로 나누어 떨어지는 배열 요소들의 곱 구하기

문제 소개

n개의 정수로 이루어진 배열 arr[n]과 하나의 정수 k가 주어졌을 때, 배열 arr[]의 요소 중 k로 나누어 떨어지는 모든 요소의 곱을 구하는 것이 이 문제의 목표입니다.

이 문제를 해결하려면 배열의 처음부터 끝까지 모든 요소를 순회하면서 각 요소가 k로 나누어 떨어지는지 확인하고, 조건을 만족하는 요소들을 곱한 결과를 변수에 저장하면 됩니다.

예를 들어 배열 arr[] = {1, 2, 3, 4, 5, 6}이 있고 k = 2라고 가정해 보겠습니다. 이 배열에서 2로 나누어 떨어지는 수는 2, 4, 6이며, 이들의 곱은 2 × 4 × 6 = 48입니다.

입력 및 출력 예시

입력

arr[] = {10, 11, 55, 2, 6, 7}
K = 11

출력

설명 − 11로 나누어 떨어지는 수는 11과 55뿐이며, 두 수의 곱은 11 × 55 = 605입니다.

입력

arr[] = {9, 8, 7, 6, 3}
K = 3

출력

설명 − 3으로 나누어 떨어지는 수는 9, 6, 3이며, 세 수의 곱은 9 × 6 × 3 = 162입니다.

문제 해결 접근 방식

배열의 첫 번째 요소부터 마지막 요소까지 전체를 순회합니다.
k로 나누어 떨어지는 모든 정수를 찾습니다.
조건을 만족하는 요소들을 계속해서 곱합니다.
최종 곱을 반환합니다.
결과를 출력합니다.

알고리즘

시작
Step 1 → k로 나누어 떨어지는 모든 수를 찾는 함수 선언
    int product(int arr[], int size, int k)
        int prod = 1 선언
        반복 For int i = 0 ~ i < size, i++
            IF (arr[i] % k == 0)
                prod *= arr[i]
            End
        End
        return prod
Step 2 → main() 함수에서
    int arr[] = {2, 3, 4, 5, 6} 선언
    int size = sizeof(arr) / sizeof(arr[0]) 선언
    int k = 2 설정
    product(arr, size, k) 호출
종료

C++ 구현 예제

#include <iostream>
using namespace std;
// 배열에서 k로 나누어 떨어지는 요소들의 곱을 구하는 함수
int product(int arr[], int size, int k){
    int prod = 1;
    for (int i = 0; i < size; i++){
        if (arr[i] % k == 0){
            prod *= arr[i];
        }
    }
    return prod;
}
int main(){
    int arr[] = {2, 3, 4, 5, 6};
    int size = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    cout<<"product of elements are : "<<product(arr, size, k);
    return 0;
}

출력 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −

product of elements are : 48

복잡도 분석

시간 복잡도: O(n) — 배열의 모든 요소를 한 번씩 순회하므로 배열의 크기에 비례합니다.

공간 복잡도: O(1) — 곱을 저장하는 변수 하나만 사용하므로 추가 메모리가 필요하지 않습니다.

참고 사항

배열 요소들의 곱은 값이 매우 빠르게 커질 수 있습니다. 따라서 실제 응용 환경에서는 정수 오버플로우를 방지하기 위해 long long과 같은 더 큰 자료형을 사용하는 것이 안전합니다. 또한 k로 나누어 떨어지는 요소가 하나도 없는 경우 초기값인 1이 반환되므로, 필요에 따라 이 경우를 별도로 처리하는 로직을 추가할 수 있습니다.