C++에서 k로 나누어 떨어지는 배열 요소 개수 구하기

양의 정수로 이루어진 배열과 정수 변수 k가 주어졌을 때, 배열 내에서 주어진 값 k로 나누어 떨어지는 요소의 개수를 계산하는 것이 이번 문제의 목표입니다.

예제를 통한 문제 이해

입력 − int arr[] = {4, 2, 6, 1, 3, 8, 10, 9}, k = 2

출력 − 2로 나누어 떨어지는 배열 요소의 개수: 5

설명 − 배열의 각 요소를 k 값으로 나누고 나머지가 0인지 확인합니다. 4, 2, 6, 8, 10은 2로 나누어 떨어지지만, 1, 3, 9는 나누어 떨어지지 않습니다. 따라서 k, 즉 2로 완전히 나누어 떨어지는 요소는 총 5개입니다.

입력 − int arr[] = {3, 2, 9, 15, 0, 8, 10}, k = 3

출력 − 3으로 나누어 떨어지는 배열 요소의 개수: 3

설명 − 마찬가지로 각 요소를 k로 나누어 나머지가 0인지 검사합니다. 3, 9, 15는 3으로 나누어 떨어지며, 2, 8, 10은 나누어 떨어지지 않습니다(0은 이 예제에서 특수한 경우로 처리합니다). 따라서 k, 즉 3으로 나누어 떨어지는 요소는 총 3개입니다.

프로그램에 사용된 접근 방식

하나의 문제를 해결하는 데에는 여러 가지 방법이 있을 수 있습니다. 먼저 가장 기본적인 단순(naive) 접근법부터 살펴보겠습니다.

정수 요소로 이루어진 배열과 정수 변수 k를 입력받습니다.
배열의 길이를 계산하고, 이후 처리를 위해 해당 데이터를 함수에 전달합니다.
k로 나누어 떨어지는 요소의 개수를 저장할 임시 변수 count를 선언합니다.
0부터 배열 길이까지 FOR 반복문을 실행합니다.
반복문 안에서 arr[i] % k == 0 조건을 검사하고, 참이면 count를 1 증가시킵니다.
count 값을 반환합니다.
결과를 출력합니다.

효율적인 접근 방식

정수형 벡터(vector)에 요소를 입력받고 정수 변수 k를 선언합니다.
k로 나누어 떨어지는 요소의 개수를 저장할 임시 변수 count를 선언합니다.
STL의 내장 함수 count_if()를 호출하여 그 결과를 count에 저장합니다. count_if()는 vector.begin()과 vector.end()를 인자로 받아 전체 요소를 순회하면서 i % k가 0인 경우를 자동으로 셉니다.
결과를 출력합니다.

예제 (단순 접근법)

#include <bits/stdc++.h>
using namespace std;
int divisible_k(int arr[], int size, int k){
    int count = 0;
    for(int i = 0; i<size; i++){
        if(arr[i]%k==0){
            count++;
        }
    }
    return count;
}
int main(){
    int arr[] = {4, 2, 6, 1, 3, 8, 10, 9};
    int k = 2;
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"Count the number of elements in an array which are divisible by "<<k<<" are: "<<divisible_k(arr, size, k);
    return 0;
}

출력

위 코드를 실행하면 다음과 같은 결과가 생성됩니다 −

Count the number of elements in an array which are divisible by 2 are: 5

예제 (효율적인 접근법)

#include <bits/stdc++.h>
using namespace std;
int main(){
    vector<int> vec = {4, 2, 6, 1, 3, 8, 10, 9};
    int count = count_if(vec.begin(), vec.end(), [](int i, int k = 2) { return i % k == 0; });
    cout<<"Count the number of elements in an array which are divisible by k are: "<<count;
    return 0;
}

출력

위 코드를 실행하면 다음과 같은 결과가 생성됩니다 −

Count the number of elements in an array which are divisible by 2 are: 5

복잡도 분석

두 접근 방식 모두 배열의 모든 요소를 한 번씩 확인하므로 시간 복잡도는 O(n)이며, 카운트용 변수 하나만 사용하므로 공간 복잡도는 O(1)입니다. 두 방법의 차이는 성능이 아니라 코드의 간결성에 있습니다. STL의 count_if()를 활용하면 반복문을 직접 작성하지 않아도 되기 때문에 코드가 더 짧아지고 가독성이 크게 향상됩니다.