C++ ] leetCode 861 - Score After Flipping Matrix

 

 

리트코드 861 문제

 

 

You are given an m x n binary matrix grid.

A move consists of choosing any row or column and toggling each value in that row or column (i.e., changing all 0's to 1's, and all 1's to 0's).

Every row of the matrix is interpreted as a binary number, and the score of the matrix is the sum of these numbers. Return the highest possible score after making any number of moves (including zero moves).

 

 

Example 1:

 

• Input: grid = [[0,0,1,1],[1,0,1,0],[1,1,0,0]]
• Output: 39
• Explanation: 0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39

 

 

Example 2:

• Input: grid = [[0]]
• Output: 1

 

 

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 20
• grid[i][j] is either 0 or 1.

 

이건 각 행의 바이너리 숫자를 구한뒤 다 더하는 것보다는, i 열은 2의 (row - i - 1)승 자리이니 각 열의 최종 1의 개수를 카운트 해 2^n 자리 값을 구한뒤 다 더하는 방법이 편하다.

 

1. 먼저 0열은 무조건 다 1로 채워진다고 보면 된다. 그래서 먼저 col * (1 << (row - 1));로 구해놓는다.

 

2. 1열부터 모든행을 순회해하는데 해당 행의 0열 값이 0이면 해당 셀을 반전시키고 1의 개수를 ones에 카운트한다.

 

3. 행 순회를 마쳤으면 1의 개수와 0의 개수 중 많은 것을 취해 해당 열의 2^n 자리 값을 구해 누적한다.

 

4. 마지막 열까지 2, 3번을 반복한다.

 

class Solution {
public:
    int matrixScore(vector<vector<int>>& grid) {
        int col = grid.size();
        int row = grid[0].size();
        int ret = col * (1 << (row - 1));

        for (int j = 1; j < row; j++) {
            int max, ones = 0;
            for (int i = 0; i < col; i++) {
                if (grid[i][0] == 0) grid[i][j] ^= 1;
                if (grid[i][j] == 1) ones++;
            }
            max = ones > col - ones ? ones : col - ones;
            ret += max * (1 << (row - j - 1));
        }

        return ret;
    }
};