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

0과 1로만 이루어진 행렬이 주어졌다고 가정해 보겠습니다. 우리는 행렬에서 원하는 만큼의 열을 선택해 해당 열에 속한 모든 셀의 값을 한 번에 뒤집을 수 있습니다. 셀을 뒤집으면 값이 0은 1로, 1은 0으로 바뀝니다. 이렇게 여러 차례 열을 뒤집은 뒤, 행 내부의 모든 값이 서로 같은 행이 최대 몇 개가 될 수 있는지 구하는 것이 이 문제의 목표입니다.

문제 예시

예를 들어 행렬이 다음과 같다고 해보겠습니다.

이 경우 출력은 2입니다. 앞의 두 열을 뒤집으면 두 번째 행은 [1, 1, 1]이 되고, 세 번째 행은 [0, 0, 0]이 되어 마지막 두 행의 모든 값이 같아지기 때문입니다.

접근 방법

핵심 아이디어는 간단합니다. 어떤 행이든 열을 적절히 뒤집으면 그 행은 전부 0 또는 전부 1로 만들 수 있습니다. 이때 함께 같은 모양이 되는 다른 행들은, 기준 행과 완전히 동일하거나 완전히 반대(모든 비트가 뒤집힌) 패턴을 가진 행들뿐입니다. 따라서 각 행을 기준으로 '자신과 동일한 행의 개수 + 자신의 반전과 동일한 행의 개수'를 계산하고, 그중 최댓값을 구하면 됩니다.

여기서 각 비트를 1과 XOR 연산하면 해당 비트가 반전됩니다(0 ^ 1 = 1, 1 ^ 1 = 0). 이 성질을 활용하면 한 행의 반전 리스트를 아주 간단하게 만들 수 있습니다.

알고리즘 단계

• x := 입력 행렬, m := 행의 개수, n := 열의 개수, r := 0으로 초기화합니다.
• x의 각 행 i에 대해 다음을 반복합니다.
  • c := 0으로 초기화합니다.
  • a := 행 i의 모든 원소 l에 대해 l XOR 1을 저장한 리스트, 즉 i의 반전 행을 만듭니다.
  • x의 각 행 j에 대해, j가 i와 같거나 a와 같으면 c를 1씩 증가시킵니다.
  • r := c와 r 중 더 큰 값을 저장합니다.
• 모든 행을 확인한 뒤 r을 반환합니다.

이 알고리즘의 시간 복잡도는 행의 개수를 m, 열의 개수를 n이라 할 때 O(m² × n)입니다. 모든 행 쌍을 서로 비교해야 하기 때문입니다.

구현 예제

아래 코드를 통해 더 잘 이해해 보겠습니다.

class Solution(object):
    def maxEqualRowsAfterFlips(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()
print(ob.maxEqualRowsAfterFlips([[0,0,0],[0,0,1],[1,1,0]]))

실행 결과

입력:

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

출력:

2