이 문제에서는 각 행이 오름차순으로 정렬되어 있는 이진 행렬(binary matrix)이 주어집니다. 우리의 과제는 이 행렬에서 1의 개수가 가장 많은 행의 번호를 찾는 것입니다.
먼저 예시를 통해 문제를 이해해 보겠습니다.
입력
binMat[][] = {
1, 1, 1, 1
0, 0, 0, 0
0, 0, 0, 1
0, 0, 1, 1
}출력
1
위 예시에서 첫 번째 행은 1이 4개로 가장 많으므로 결과는 1이 됩니다.
방법 1: 단순 카운트 (완전 탐색)
가장 직관적인 해결 방법은 각 행에 포함된 1의 총 개수를 하나씩 세어, 그중 1의 개수가 가장 많은 행의 번호를 반환하는 것입니다. 이 방법의 시간 복잡도는 O(R×C)입니다.
예제 코드
#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;
}출력
The number of row with maximum number of 1's is 1
방법 2: 이진 탐색 활용
각 행이 정렬되어 있다는 특성을 활용하면 성능을 개선할 수 있습니다. 각 행에 대해 이진 탐색(binary search)을 적용하여 해당 행에서 처음으로 1이 나타나는 위치를 찾는 것입니다.
행에 포함된 1의 개수는 행 크기 − 첫 번째 1의 인덱스 공식으로 계산할 수 있습니다. 이 값을 이용해 각 행의 1 개수를 구한 뒤, 1이 가장 많은 행을 반환하면 됩니다. 시간 복잡도는 O(R×log C)로 향상됩니다.
예제 코드
#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
방법 3: 최적화된 이진 탐색
위 방법에 한 단계 더 최적화를 적용할 수 있습니다. 바로 첫 번째 1의 인덱스를 기준으로, 현재 행이 이전 행보다 더 많은 1을 가지고 있는지 미리 확인하는 것입니다. 조건을 만족하는 경우에만 이진 탐색을 수행하되, 탐색 범위를 0부터 이전 행의 첫 번째 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
마무리
정렬된 이진 행렬에서 1이 가장 많은 행을 찾는 문제는 단순 카운트 O(R×C), 이진 탐색 O(R×log C), 최적화된 이진 탐색 순으로 점진적으로 성능을 개선할 수 있습니다. 핵심은 '각 행이 정렬되어 있다'는 조건을 적극적으로 활용해 탐색 범위를 줄이는 것입니다.