C++를 사용하여 최대 개수가 1인 행 찾기

이 문제에서는 각 행의 요소가 정렬된 이진 행렬이 제공됩니다. 우리의 임무는 최대 개수가 1인 행을 찾는 것입니다. .

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

입력

mat[][] = {{ 0 1 1 1}
   {1 1 1 1}
   {0 0 0 1}
   {0 0 1 1}}

출력

1

설명

The count of 1’s in each row of the matrix :
Row 0 : 3
Row 1 : 4
Row 2 : 1
Row 3 : 2

솔루션 접근 방식

이 문제에 대한 간단한 해결책은 처음 1의 인덱스가 가장 작은 행을 찾는 것입니다.

한 가지 접근 방식은 행 순회를 사용하여 행에서 최대 개수 1을 반환하는 첫 번째 1의 인덱스를 찾는 것입니다. 그런 다음 최대 1개의 행을 반환합니다.

또 다른 접근 방식은 이진 검색을 사용하는 것입니다. 각 행에서 처음 1의 발생을 찾습니다. 그런 다음 최대값이 1인 값을 반환합니다.

예시

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

#include <iostream>
using namespace std;
#define R 4
#define C 4
int findFirst1BinSearch(bool arr[], int low, int high){
   if(high >= low){
      int mid = low + (high - low)/2;
      if ( ( mid == 0 || arr[mid-1] == 0) && arr[mid] == 1)
         return mid;
      else if (arr[mid] == 0)
         return findFirst1BinSearch(arr, (mid + 1), high);
      else
         return findFirst1BinSearch(arr, low, (mid -1));
   }
   return -1;
}
int findMaxOneRow(bool mat[R][C]){
   int max1RowIndex = 0, max = -1;
   for (int i = 0; i < R; i++){
      int first1Index = findFirst1BinSearch(mat[i], 0, C-1);
      if (first1Index != -1 && C-first1Index > max){
         max = C - first1Index;
         max1RowIndex = i;
      }
   }
   return max1RowIndex;
}
int main(){
   bool mat[R][C] = { {0, 1, 1, 1},
   {1, 1, 1, 1},
   {0, 0, 1, 1},
   {0, 0, 0, 1}};
   cout<<"The row with maximum number of 1's in the matrix is "<<findMaxOneRow(mat);
   return 0;
}

출력

The row with maximum number of 1's in the matrix is 1