861. Score After Flipping Matrix

Score After Flipping Matrix - LeetCode

0과 1로 이루어진 2차원 배열이 주어진다.

2차원 배열에 대한 한 가지 조작이 가능한데, 그 조작은 행 또는 열을 고르고 그 안의 모든 0은 1로, 1은 0으로 스위칭하는 것이다.

조작을 수행하는 횟수는 제한이 없다.

해당 조작을 통해 2차원 배열을 조작하고, 행을 구성하는 1과 0을 2진수 취급한 뒤 모든 행의 합이 가장 크게 되는 경우 그 합을 반환하는 문제다.

 

예시

초기 배열이 좌측 상단의 2차원 배열이라면

1. 1행에 대해 조작한다.
2. 3열에 대해 조작한다.
3. 4열에 대해 조작한다.

이렇게 조작했을 때 우측 하단의 배열이 나오는데, 이때 합은 1111(2) + 1011(2) + 1111(2) = 39로 가장 크게 되는 경우다.

1. Greedy

from typing import *


class Solution:
    def matrixScore(self, grid: List[List[int]]) -> int:
        def switch(input_list):
            return list(map(lambda x: 1 if x == 0 else 0, input_list))

        height, width = len(grid), len(grid[0])

        for i in range(height):
            if grid[i][0] == 0:
                result = switch(grid[i])
                grid[i] = result

        for j in range(1, width):
            temp = []
            for i in range(height):
                temp.append(grid[i][j])
            result = None
            if height - sum(temp) > height // 2:
                result = switch(temp)
            if result:
                for i in range(height):
                    grid[i][j] = result[i]

        answer = 0
        for i in range(height):
            temp = grid[i]
            temp = list(map(str, temp))
            answer += int("".join(temp), 2)

        return answer

그리디 하게 접근해서 해결할 수 있다.

• 우선 행을 2진수로 만들어서 가장 큰 값이 되게 하려면 0열을 무조건 1로 만들어야 한다.
• 왜냐면 1000(2) > 0111(2)라는N진법 숫자 특징 때문에 상위 비트가 무조건 켜져 있는 게 다른 비트가 전부 켜져 있는 것보다 크기 때문이다.
• 그러니깐 1차적으로 0열을 순회하면서 비트가 0인 행을 전부 뒤집는다. 이렇게 하면 0열은 전부 1로 채워진다.
• 이후 1열부터 순회를 하는데 해당 열의 0과 1의 개수를 센 뒤, 0이 더 많다면 해당 열을 뒤집는다.

 

예를 들어서 0열 ~ 3열까지 있는 오른쪽 배열을 본다면...

• 우선적으로 0열을 모두 1로 바꾸어 줘야 하기 때문에 0행을 뒤집어 0열을 모두 1로 만든다.
• 그다음 1열부터 3열까지 탐색을 하는데 1, 3열의 경우는 0이 2개 1이 한 개이기 때문에 뒤집어준다.
• 2열의 경우는 1이 2개 0이 한 개이기 때문에 유지한다.

 

이렇게 하면 결과 배열은 오른쪽 배열에서 (2,2)가 0이고 (1,2)가 1인 상태가 되는데 이때가 최댓값이 된다.

결국 순서 상관없이 그리디 한 접근 방법으로 왼쪽 열부터 최대한 1을 많이 가지도록 조작해주면 원하는 최댓값을 만드는 배열을 만들 수 있다.