문제 설명
2차원 이진 행렬(binary matrix)이 주어졌다고 가정해 봅시다. 우리는 행렬의 임의의 행 또는 열에 속한 모든 비트를 한 번에 뒤집을 수 있으며, 이 연산은 원하는 만큼 여러 번 수행할 수 있습니다. 모든 연산이 끝난 후 각 행을 하나의 이진수로 해석했을 때, 만들 수 있는 숫자들의 최대 합계를 구하는 것이 이 문제의 목표입니다.
예를 들어 입력 행렬이 다음과 같다고 해 보겠습니다.
| 0 | 1 | 0 |
| 0 | 0 | 1 |
두 행을 모두 뒤집으면 각 행은 101과 110이 되고, 이때의 합계는 5 + 6 = 11로 최대가 됩니다.
접근 방법: 그리디 전략
이 문제는 그리디(greedy) 기법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 첫 번째 비트(최상위 비트)를 무조건 1로: 각 행의 맨 앞 비트가 0이라면 해당 행 전체를 뒤집아 1로 만듭니다. 최상위 비트는 숫자의 값에 가장 큰 영향을 주므로 반드시 1이어야 합니다.
- 나머지 열은 1이 많은 쪽으로: 두 번째 열부터 마지막 열까지 차례대로 검사하면서, 특정 열에서 0의 개수가 1보다 많다면 그 열을 뒤집습니다.
- 최종 합산: 최적화가 끝난 행렬의 각 행을 이진수로 변환해 모두 더합니다.
알고리즘 단계
위 전략을 절차로 정리하면 다음과 같습니다.
- 행렬의 각 행 r에 대해, r[0]이 0이면 행 전체의 비트를 뒤집습니다.
- j를 1부터 열 개수 - 1까지 반복하면서 다음을 수행합니다.
- cnt := 0으로 초기화합니다.
- 모든 행 i에 대해 matrix[i][j]가 1이면 cnt를 1 증가, 0이면 1 감소시킵니다.
- 열 검사가 끝난 뒤 cnt가 음수라면(0이 더 많다면) 해당 열 전체를 뒤집습니다.
- ans := 0으로 초기화한 뒤, 각 행을 이진수로 변환(a := 2 * a + v)하여 ans에 누적합니다.
- ans를 반환합니다.
파이썬 구현 예제
class Solution:
def solve(self, matrix):
# 1단계: 각 행의 첫 비트를 1로 만든다
for r in matrix:
if r[0] == 0:
for i in range(len(r)):
r[i] = -r[i] + 1
# 2단계: 두 번째 열부터 1이 더 많도록 열을 뒤집는다
for j in range(1, len(matrix[0])):
cnt = 0
for i in range(len(matrix)):
cnt += 1 if matrix[i][j] else -1
if cnt < 0:
for i in range(len(matrix)):
matrix[i][j] = -matrix[i][j] + 1
# 3단계: 각 행을 이진수로 변환해 합산한다
ans = 0
for r in matrix:
a = 0
for v in r:
a = 2 * a + v
ans += a
return ans
ob = Solution()
matrix = [[0, 1, 0], [0, 0, 1]]
print(ob.solve(matrix))
입력
[[0, 1, 0], [0, 0, 1]]
출력
11
동작 과정 살펴보기
입력 행렬 [[0, 1, 0], [0, 0, 1]]에 위 코드를 적용하면 다음과 같이 진행됩니다.
- 행 뒤집기: 두 행 모두 첫 비트가 0이므로 각각 [1, 0, 1]과 [1, 1, 0]으로 바뀝니다.
- 열 검사: 두 번째 열은 0과 1이 하나씩이고(cnt = 0), 세 번째 열 역시 1과 0이 하나씩이므로(cnt = 0) 추가로 뒤집을 필요가 없습니다.
- 합계 계산: 101(십진수 5) + 110(십진수 6) = 11이 최종 결과가 됩니다.
복잡도 분석
행의 개수를 m, 열의 개수를 n이라 할 때, 모든 행과 열을 상수 번씩만 훑으므로 시간 복잡도는 O(m × n)입니다. 또한 원본 행렬을 그대로 수정하며 진행하기 때문에 추가 공간 복잡도는 O(1)로 매우 효율적입니다.