C++로 다른 배열의 요소 중 적어도 하나로 나누어 떨어지는 요소 개수 세기

두 개의 정수 배열 arr_1[]과 arr_2[]가 주어졌을 때, 첫 번째 배열의 요소 중 두 번째 배열의 요소를 약수로 가지는(즉, 나누어 떨어지는) 요소의 개수를 계산하는 것이 과제입니다. 다시 말해, arr_1[]의 각 요소가 arr_2[]의 어떤 요소로 나누어 떨어지는지 확인하고, 해당되는 요소의 총 개수를 구해야 합니다.

배열은 동일한 자료형의 요소들을 고정된 크기로 순차적으로 저장할 수 있는 자료구조입니다. 배열은 데이터 모음을 저장하는 용도로 사용되며, 같은 타입의 변수들이 모인 집합으로 생각하면 이해하기 더 쉽습니다.

예시

입력 − int arr_1[] = {1, 2, 3, 4, 5}
      arr_2[] = {2, 6, 12, 15}
출력 − count is 2

설명 − arr_1[]에는 5개의 요소가 있고, arr_2[]에는 4개의 요소가 있습니다. 이 중 2와 4만 arr_2[]의 요소인 2로 나누어 떨어지므로 개수는 2입니다.

입력 − int arr_1[] = {1, 2, 3, 4, 5}
      arr_2[] = {13, 11}
출력 − count is 0

설명 − arr_1[]에는 5개의 요소가 있고, arr_2[]에는 2개의 요소가 있습니다. arr_1[]의 어떤 요소도 13 또는 11로 나누어 떨어지지 않으므로 개수는 0입니다.

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

두 개의 배열, 예를 들어 arr_1[]과 arr_2[]를 생성합니다.
sizeof 연산자 등을 활용해 배열 길이를 계산합니다.
요소의 개수를 저장할 임시 변수를 선언합니다.
빠른 조회를 위해 unordered_set 변수(예: us)를 생성합니다.
i를 0부터 두 번째 배열의 크기보다 작을 때까지 반복하는 루프를 시작합니다.
루프 내부에서 arr_2[i]를 집합에 삽입(insert)합니다.
i를 0부터 첫 번째 배열의 크기보다 작을 때까지 반복하는 또 다른 루프를 시작합니다.
루프 내부에서 j를 1부터 j * j <= arr_1[i] 조건을 만족하는 동안 반복하는 내부 루프를 시작합니다.
내부 루프에서 arr_1[i] % j == 0이라면, 즉 j가 약수라면 us.find(j) != us.end() 또는 us.find(arr_1[i] / j) != us.end()를 확인하여 참이면 개수를 1 증가시킵니다.
조건을 만족하는 약수를 찾았다면 내부 루프를 종료(break)합니다.
개수를 반환하고 결과를 출력합니다.

예제 코드

#include <iostream>
#include <unordered_set>
using namespace std;
// 첫 번째 배열의 요소 중
// 적어도 하나의 약수가 두 번째 배열에
// 존재하는 요소의 개수를 세는 함수
int totalelements(int arr_1[], int size1, int arr_2[], int size2){
   // 요소의 개수를 저장할 변수 'result'
   int result = 0;
   // 두 번째 배열 요소의 해시 집합
   unordered_set<int> h;
   for (int i = 0; i < size2; i++){
      h.insert(arr_2[i]);
   }
   // 배열 요소를 순회하면서 약수를 찾음
   for (int i = 0; i < size1; i++){
      for (int j = 1; j * j <= arr_1[i]; j++){
         if (arr_1[i] % j == 0){
            // 해시 집합 h를 이용해
            // 해당 약수가 두 번째 배열에 존재하는지 확인
            if ((h.find(j) != h.end()) || (h.find(arr_1[i] / j)!= h.end())){
               result++;
               break;
            }
         }
      }
   }
   return result;
}
// 메인 함수
int main(){
   int arr_1[] = { 1, 2, 3, 4, 5 };
   int arr_2[] = { 2, 6, 12, 15 };
   int size1 = sizeof(arr_1) / sizeof(arr_1[0]);
   int size2 = sizeof(arr_2) / sizeof(arr_2[0]);
   cout <<"count is "<<totalelements(arr_1, size1, arr_2, size2);
   return 0;
}

출력 결과

위 코드를 실행하면 다음과 같은 출력을 얻을 수 있습니다 −

count is 2