Python으로 이진 행렬의 열을 뒤집어 값이 같은 행의 최대 개수 구하기

이진 행렬(binary matrix)이 하나 있다고 가정해 보겠습니다. 우리는 주어진 행렬에서 원하는 만큼의 열을 선택하고, 해당 열에 속한 모든 셀의 값을 뒤집을(flip) 수 있습니다. 여기서 '셀을 뒤집는다'는 것은 셀의 값을 반전시키는 것, 즉 0을 1로, 1을 0으로 바꾸는 것을 의미합니다.

목표는 몇 번의 열 뒤집기를 수행한 후, 모든 값이 동일한 행의 최대 개수를 찾는 것입니다.

예를 들어 다음과 같은 행렬이 있다고 해봅시다.

이 경우 출력 결과는 2입니다. 앞의 두 열을 뒤집으면 두 번째와 세 번째 행이 각각 [1,1,1]과 [0,0,0] 형태가 되어, 두 행 모두 모든 값이 동일해지기 때문입니다.

문제 해결 접근 방식

핵심 아이디어는 다음과 같습니다. 어떤 행이든, 그 행 자체와 그 행을 완전히 반전시킨 행(모든 비트를 XOR 연산으로 뒤집은 행)은 열 뒤집기를 통해 서로 동일하게 만들 수 있습니다. 따라서 각 행에 대해 자신과 동일하거나 정확히 반전된 형태인 행의 개수를 세면 됩니다.

구체적인 단계는 다음과 같습니다.

• x := 행렬, m := 행의 개수, n := 열의 개수, r := 0 으로 초기화합니다.
• x의 각 행 i에 대해 다음을 반복합니다.
  • 카운터 c := 0 으로 초기화합니다.
  • a := 행 i의 모든 요소 l에 대해 l XOR 1을 적용한 리스트, 즉 반전된 행을 만듭니다.
  • x의 각 행 j에 대해, j가 i와 같거나 a와 같으면 c를 1 증가시킵니다.
  • r := c와 r 중 더 큰 값으로 갱신합니다.
• 최종적으로 r을 반환합니다.

예제 코드

아래 구현을 통해 더 잘 이해해 보겠습니다.

class Solution(object):
   def solve(self, matrix):
      x = matrix
      m = len(matrix)
      n = len(matrix[0])
      r = 0
      for i in x:
         c = 0
         a = [l ^ 1 for l in i]
         for j in x:
            if j == i or j == a:
               c += 1
         r = max(c, r)
      return r

ob = Solution()
matrix = [[0,0,0],
         [0,0,1],
         [1,1,0]]
print(ob.solve(matrix))

입력

[[0,0,0],
[0,0,1],
[1,1,0]]

출력

2

코드 설명

리스트 컴프리헨션 [l ^ 1 for l in i]는 각 비트를 XOR 연산으로 반전시켜 해당 행의 '반전 버전'을 생성합니다. 이후 전체 행렬을 순회하며 현재 행과 동일한 행, 또는 반전된 행과 동일한 행의 개수를 셉니다. 이 과정을 모든 행에 대해 반복하면서 최댓값 r을 유지하면, 열 뒤집기를 통해 얻을 수 있는 동일 값 행의 최대 개수를 구할 수 있습니다.

이 알고리즘의 시간 복잡도는 O(m² × n)입니다. m개의 각 행마다 전체 행렬을 다시 순회하기 때문입니다. 행렬의 크기가 크지 않다면 충분히 효율적으로 동작합니다.