이 문제에서는 각 행이 정렬된 이진 행렬이 제공됩니다. 우리의 임무는 최대 개수가 1인 이진 행렬의 행 번호를 찾는 것입니다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력
binMat[][] = {
1, 1, 1, 1
0, 0, 0, 0
0, 0, 0, 1
0, 0, 1, 1
} 출력
1
솔루션 접근 방식
이 문제에 대한 간단한 해결책은 각 행의 총 1 수를 계산하는 것입니다. 그런 다음 최대 1 카운트의 행 번호를 반환합니다.
우리 솔루션의 작동을 설명하는 프로그램
예시
#include <iostream>
using namespace std;
#define R 4
#define C 4
int findMax1Row(bool mat[R][C]) {
int max1Row = 0, max1Count = -1;
int i, index;
for (i = 0; i < R; i++) {
int oneCount = 0;
for(int j = 0; j < C; j++){
if(mat[i][j])
oneCount++;
}
if(oneCount > max1Count){
max1Count = oneCount;
max1Row = i;
}
}
return (max1Row + 1);
}
int main() {
bool mat[R][C] = {
{0, 1, 1, 1},
{0, 0, 1, 1},
{0, 0, 0, 1},
{0, 0, 0, 0}
};
cout<<"The number of row with maximum number of 1's is "<<findMax1Row(mat);
return 0;
} 출력
최대 개수가 1인 행의 수는 1입니다. 문제에 대한 더 나은 솔루션은 각 행에서 이진 검색을 사용하여 행에서 1이 처음 나타나는 것을 찾는 것입니다. 행의 숫자 1은 행 크기 - 처음 1의 인덱스를 사용하여 찾을 수 있습니다. 이를 사용하여 각 행의 1 개수를 찾은 다음 최대 개수 1의 행을 반환할 수 있습니다.
우리 솔루션의 작동을 설명하는 프로그램
예시
#include <iostream>
using namespace std;
#define R 4
#define C 4
int binarySearch1Row(bool arr[], int start, int end) {
if(end >= start) {
int mid = start + (end - start)/2;
if ( ( mid == 0 || arr[mid-1] == 0) && arr[mid] == 1)
return mid;
else if (arr[mid] == 0)
return binarySearch1Row(arr, (mid + 1), end);
else
return binarySearch1Row(arr, start, (mid -1));
}
return -1;
}
int findMax1Row(bool mat[R][C]) {
int max1Row = 0, max1Count = -1;
int i, index;
for (i = 0; i < R; i++) {
index = binarySearch1Row(mat[i], 0, C-1);
if (index != -1 && ( C-index) > max1Count) {
max1Count = C - index;
max1Row = i;
}
}
return (max1Row + 1);
}
int main() {
bool mat[R][C] = {
{0, 1, 1, 1},
{0, 0, 1, 1},
{0, 0, 0, 1},
{0, 0, 0, 0}
};
cout<<"The number of row with maximum number of 1's is "<<findMax1Row(mat);
return 0;
} 출력
The number of row with maximum number of 1's is 1
위의 접근 방식에 추가된 최적화는 첫 번째 1의 인덱스를 사용하여 현재 행에 이전 행보다 더 많은 1이 있는지 확인할 수 있습니다. 1이 더 많으면 이진 검색을 수행하지만 마지막 행의 0에서 처음 1의 인덱스까지 수행합니다.
이렇게 하면 현재 것보다 1이 작은 행에서 1의 수를 계산하는 오버헤드를 줄일 수 있습니다.
우리 솔루션의 작동을 설명하는 프로그램
예시
#include <iostream>
using namespace std;
#define R 4
#define C 4
int binarySearch1Row(bool arr[], int start, int end) {
if(end >= start) {
int mid = start + (end - start)/2;
if ( ( mid == 0 || arr[mid-1] == 0) && arr[mid] == 1)
return mid;
else if (arr[mid] == 0)
return binarySearch1Row(arr, (mid + 1), end);
else
return binarySearch1Row(arr, start, (mid -1));
}
return -1;
}
int findMax1Row(bool mat[R][C]) {
int i, index;
int max1Row = 0;
int max1Count = binarySearch1Row(mat[0], 0, C - 1);
for (i = 1; i < R; i++){
if (max1Count != -1 && mat[i][C - max1Count - 1] == 1) {
index = binarySearch1Row (mat[i], 0, C - max1Count);
if (index != -1 && C - index > max1Count) {
max1Count = C - index;
max1Row = i;
}
}
else
max1Count = binarySearch1Row(mat[i], 0, C - 1);
}
return (max1Row + 1);
}
int main() {
bool mat[R][C] = {
{0, 1, 1, 1},
{0, 0, 0, 1},
{0, 0, 1, 1},
{0, 0, 0, 0}
};
cout<<"The number of row with maximum number of 1's is "<<findMax1Row(mat);
return 0;
} 출력
The number of row with maximum number of 1's is 1