이 문제에서는 각 행의 요소가 오름차순으로 정렬된 이진 행렬(binary matrix)이 주어집니다. 우리의 목표는 1의 개수가 가장 많은 행을 찾는 것입니다.
문제 예시
구체적인 예시를 통해 문제를 이해해 보겠습니다.
입력:
mat[][] = {{ 0 1 1 1}
{1 1 1 1}
{0 0 0 1}
{0 0 1 1}}
출력:
1
설명:
행렬의 각 행에 포함된 1의 개수 : 0행 : 3개 1행 : 4개 2행 : 1개 3행 : 2개
위 예시에서 1행(두 번째 행)에는 1이 총 4개로 가장 많으므로 정답은 인덱스 1이 됩니다.
해결 접근 방법
이 문제를 해결하는 핵심 아이디어는 “첫 번째 1이 등장하는 인덱스가 가장 작은 행”을 찾는 것입니다. 각 행이 정렬되어 있기 때문에, 첫 번째 1의 위치가 앞쪽일수록 그 행에 포함된 1의 개수도 더 많습니다.
1. 행 단위 순회 방식
각 행을 처음부터 끝까지 순회하면서 첫 번째 1의 인덱스를 찾습니다. 첫 번째 1의 위치를 알면 전체 열의 수에서 그 인덱스를 빼서 해당 행에 포함된 1의 개수를 계산할 수 있습니다. 모든 행을 확인한 뒤, 1의 개수가 가장 많은 행을 반환합니다.
2. 이진 탐색(Binary Search) 방식
각 행이 정렬되어 있다는 특성을 활용하면 이진 탐색을 통해 첫 번째 1의 위치를 O(log C) 시간 안에 찾을 수 있습니다. 각 행마다 이진 탐색을 수행하여 첫 번째 1의 인덱스를 구하고, 그중 1의 개수가 최대인 행을 반환합니다.
C++ 구현 예제
다음은 위에서 설명한 이진 탐색 기반 솔루션의 동작을 보여주는 C++ 프로그램입니다.
#include <iostream>
using namespace std;
#define R 4
#define C 4
// 이진 탐색으로 배열에서 첫 번째 1의 인덱스를 찾는 함수
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;
}
// 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, 0, 1},
{0, 0, 1, 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
프로그램을 실행하면 행렬에서 1의 개수가 가장 많은 행이 인덱스 1(두 번째 행)임을 확인할 수 있습니다.
시간 복잡도 분석
단순 순회 방식: 각 행을 처음부터 끝까지 확인해야 하므로 O(R × C)의 시간 복잡도를 가집니다.
이진 탐색 방식: 각 행마다 O(log C)의 탐색을 R번 수행하므로 총 O(R log C)의 시간 복잡도를 가집니다. 행렬의 크기가 커질수록 단순 순회 방식보다 훨씬 효율적으로 동작합니다.