C++에서 리스트의 모든 요소가 특정 숫자로 나누어 떨어지는지 확인하는 방법

이 문제에서는 n개의 숫자로 이루어진 리스트와 하나의 숫자가 주어집니다. 우리의 과제는 리스트의 모든 요소가 주어진 숫자로 나누어 떨어지는지 확인하는 것입니다.

즉, 리스트의 모든 요소를 주어진 숫자로 나눴을 때 나머지가 0이 되는지 하나씩 검사해야 합니다.

예제로 문제 이해하기

입력: list[] = [4, 10, 6, 5, 9], num = 5

출력: No

설명:

요소 4, 6, 9는 5로 나누어 떨어지지 않으므로 조건을 만족하지 않습니다.

해결 접근 방식

이 문제를 해결하려면 리스트의 각 요소가 num으로 나누어 떨어지는지 순서대로 확인해야 합니다. 모든 요소가 num으로 나누어 떨어지면 true를 반환하고, 단 하나라도 나누어 떨어지지 않는 요소가 있다면 즉시 false를 반환합니다.

알고리즘

1단계: i를 0부터 n-1까지 반복합니다(n은 리스트의 길이).

1.1단계: list[i] % num != 0이면 false를 반환합니다.
1.2단계: 그렇지 않고 list[i] % num == 0이면 다음 요소로 계속 진행합니다.

2단계: 모든 요소 검사가 끝나면 true를 반환합니다.

솔루션 구현 예제

#include <iostream>
using namespace std;

bool isListDivNum(int list[], int num, int size)
{
   for (int i = 0; i < size; i++) {
      if (list[i] % num != 0)
         return false;
   }
   return true;
}

int main() {
   
   int list[] = {762, 9, 123, 99};
   int num = 3;
   int size = (sizeof(list) / sizeof(list[0]));
   if (isListDivNum(list, num, size))
      cout<<"All elements of the list are divisible by number";
   else
      cout<<"All elements of the list are not divisible by number";

   return 0;
}

출력 −

All elements of the list are divisible by number

코드 설명

isListDivNum 함수는 리스트의 각 요소를 num으로 나눈 나머지를 검사합니다. 나머지가 0이 아닌 요소를 발견하는 즉시 false를 반환하여 불필요한 반복을 줄입니다. 모든 요소가 검사를 통과하면 true를 반환합니다.

main 함수에서는 sizeof(list) / sizeof(list[0]) 연산으로 배열의 크기를 계산한 뒤 함수를 호출하고, 결과에 따라 적절한 메시지를 출력합니다.

시간 복잡도

리스트의 모든 요소를 한 번씩만 검사하므로 시간 복잡도는 O(n)이며, 추가 메모리 사용 없이 수행되므로 공간 복잡도는 O(1)입니다.