C++를 사용하여 0의 개수 찾기

이 문제에서는 0과 1로만 구성된 이진 배열 bin[]이 제공됩니다. 우리의 임무는 0의 개수를 찾는 것입니다. .

배열은 정렬됩니다. 즉, 모든 0은 1 뒤에 함께 정렬됩니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력

arr[] = {1, 1, 1, 0, 0, 0, 0}

출력

4

솔루션 접근 방식

문제에 대한 간단한 해결책은 배열이 정렬된다는 사실을 사용하는 것입니다. 즉, 배열에서 0이 처음 나타나는 것을 사용하여 배열의 0의 수를 찾을 수 있습니다. 첫 번째 발생 이후와 마찬가지로 모든 값은 0이 됩니다.

배열에서 0의 첫 번째 항목을 찾는 데 사용됩니다. 검색 알고리즘을 사용할 수 있습니다.

선형 검색 - 첫 번째 0에 대한 선형 검색에서 첫 번째 0이 발견되지 않을 때까지 전체 배열을 순회한 다음 배열의 첫 번째 항목과 크기를 사용하여 개수를 반환합니다. 이 솔루션을 사용하여 문제의 시간 복잡도를 O(N)으로 만듭니다.

예시

솔루션 작동을 설명하는 프로그램

#include <iostream>
using namespace std;
int findFirstZero(int arr[], int n){
   for(int i = 0; i < n; i++){
      if(arr[i] == 0){
         return i;
      }
   }
   return -1;
}
int countZerosArr(int arr[], int n){
   int firstOccZero = findFirstZero(arr, n);
   if (firstOccZero == -1)
      return 0;
      return (n - firstOccZero);
   }
int main(){
   int arr[] = {1, 1, 1, 1, 0, 0, 0, 0, 0};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The count of zeros in array is "<<countZerosArr(arr, n);
   return 0;
}

출력

The count of zeros in array is 5

이진 검색 - 이진 검색에서는 중간에 있는 요소가 1인지 0인지에 따라 배열의 섹션을 나누어 처음 0을 찾습니다. 그리고 0이 처음 나타나는 인덱스를 반환합니다.

예시

솔루션 작동을 설명하는 프로그램

#include <iostream>
using namespace std;
int findFirstZero(int arr[], int start, int end){
   if (end >= start){
      int mid = start + (end - start) / 2;
      if ((mid == 0 || arr[mid - 1] == 1) && arr[mid] == 0)
         return mid;
      if (arr[mid] == 1)
         return findFirstZero(arr, (mid + 1), end);
      else
         return findFirstZero(arr, start, (mid -1));
   }
   return -1;
}
int countZerosArr(int arr[], int n){
   int firstOccZero = findFirstZero(arr, 0, n - 1);
   if (firstOccZero == -1)
      return 0;
      return (n - firstOccZero);
}
int main(){
   int arr[] = {1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The count of zeros in array is "<<countZerosArr(arr, n);
   return 0;
}

출력

The count of zeros in array is 7