Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬으로 목표 행렬을 만들기 위한 최소 열 뒤집기 횟수 계산하기

행렬 M과 같은 행·열 크기를 가진 목표 행렬 T가 있다고 가정해 보겠습니다. 여기서 '연산'이란 행렬의 특정 열 하나를 뒤집는 작업으로, 해당 열에 있는 모든 1은 0으로, 모든 0은 1로 바뀝니다. 이때 행의 순서는 자유롭게 재배열할 수 있으며 비용이 들지 않습니다. 이 조건에서 M을 T로 변환하는 데 필요한 최소 연산 횟수를 구하는 프로그램을 작성해야 하며, 변환이 불가능하다면 -1을 반환합니다.

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

M =

00
10
11

T =

01
10
11

이 경우 출력은 1입니다. 먼저 행의 순서를 다음처럼 재배열합니다.

00
11
10

그다음 첫 번째 열(index 0)을 한 번 뒤집으면,

01
10
11

목표 행렬 T와 정확히 일치하게 됩니다.

풀이 접근 방법

이 문제는 각 행을 이진수 값으로 취급하고 XOR 연산을 활용하면 효율적으로 해결할 수 있습니다. 단계별로 살펴보겠습니다.

  • 빈 리스트 nums1과 nums2를 준비합니다.
  • 행렬 M의 각 행에 대해:
    • ths = 0으로 초기화합니다.
    • 행이 빌 때까지 마지막 원소를 꺼내 ths = (ths * 2) + 원소로 갱신합니다.
    • 완성된 값을 nums1의 끝에 추가합니다.
  • 목표 행렬 T에 대해서도 동일한 과정을 수행해 nums2를 만듭니다.
  • ret = 무한대(infinity)로 초기화합니다.
  • nums1의 각 값 num에 대해:
    • cts: nums1의 원소별 빈도수를 저장한 맵(Counter)을 생성하고, cts[num] -= 1로 현재 선택된 행을 제외합니다.
    • my_xor = num XOR nums2[0]을 계산합니다. 이 값은 각 행에 적용해야 할 뒤집기 패턴을 의미합니다.
    • i를 1부터 nums2의 크기까지 순회하며:
      • needed = my_xor XOR nums2[i]를 계산합니다.
      • cts[needed]가 0이라면 필요한 행 패턴이 존재하지 않으므로 반복문을 탈출합니다.
      • 그렇지 않다면 cts[needed] -= 1로 해당 패턴을 소진합니다.
    • 반복문이 중단 없이 완료되면(모든 행이 매칭되면) ret = min(ret, my_xor의 1비트 개수)로 갱신합니다. 1비트 개수가 곧 뒤집어야 할 열의 개수입니다.
  • ret가 무한대가 아니면 ret을, 그렇지 않으면 -1을 반환합니다.

구현 예제 코드

class Solution:
   def solve(self, matrix, target):
      nums1 = []
      nums2 = []
      for row in matrix:
         ths = 0
         while row:
            ths = (ths<<1) + row.pop()
         nums1.append(ths)
      for row in target:
         ths = 0
         while row:
            ths = (ths<<1) + row.pop()
         nums2.append(ths)
      ret=float('inf')
      from collections import Counter
      for num in nums1:
         cts = Counter(nums1)
         cts[num] -= 1
         my_xor = num^nums2[0]
         for i in range(1,len(nums2)):
            needed = my_xor^nums2[i]
            if not cts[needed]:
               break
            cts[needed]-=1
         else:
            ret=min(ret,bin(my_xor).count('1'))
      return ret if ret!=float('inf') else -1
ob = Solution()
M = [
   [0, 0],
   [1, 0],
   [1, 1]
]
T = [
   [0, 1],
   [1, 0],
   [1, 1]
]
print(ob.solve(M,T))

입력

M = [[0, 0],[1, 0],[1, 1]]
T = [[0, 1],[1, 0],[1, 1]]

출력

1

핵심 포인트 정리

  • 행 → 이진수 변환: 각 행을 정수 값으로 변환하면 행 비교와 XOR 계산이 간단해집니다.
  • XOR의 역할: 두 행 사이의 XOR 결과는 어떤 열들을 뒤집어야 하는지를 나타냅니다.
  • 1비트 개수 = 연산 횟수: XOR 값에서 1인 비트의 개수가 곧 뒤집어야 할 열의 수입니다.
  • Counter 활용: 행 패턴의 빈도를 관리해 모든 행이 목표 행렬과 매칭 가능한지 효율적으로 검증합니다.