[LeetCode] 861. Score After Flipping Matrix

https://leetcode.com/problems/score-after-flipping-matrix/description/

leetcode - Score After Flipping Matrix

문제 유형 : 행렬, 비트마스킹, 그리디

문제 난이도 : Medium

 

문제

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).

 

m x n의 바이너리 행렬이 grid가 주어진다.

당신은 한 행 또는 열 째로 뒤집을 수 있다.

11011 -> 00100. 이런 식으로말이다.

 

각 열별로 끊어서 이진수를 읽는다 할때, 그 수들의 합이 최대가 되도록 하시오.

몇 번이고 뒤집어도 됩니다.

 

풀이

1000(2)는 0111(2)보다 크다.

즉, 최상위 비트가 켜져있는 것이 우선이다. 하위 비트들을 아무리 켜봐야, 최상위 비트 하나 켜져있는 것이 더 크다.

그러므로, 각 열을 보면서, 맨 첫번째 수가 0이면, 그 열을 전체 뒤집는다.

그리고, 이제 행 단위로 잘라서 보면 되는데, 행들도 같이 뒤집어줘야 하므로,

1행부터 각각 확인하면서, 1의 개수가 0의개수보다 적은 열은 비트를 반전시킨다.

 

열별로 읽으면서 수들의 합을 구한다.

 

코드

C++

class Solution {
private:
    int n, m;
public:
    void flipCol(int col, vector<vector<int>> &grid) {
        for(int i = 0; i < m; i++) {
            grid[i][col] ^= 1;
        }
    }
    void flipRow(int row, vector<vector<int>> &grid) {
        for(int i = 0; i < n; i++) {
            grid[row][i] ^= 1;
        }
    }
    int matrixScore(vector<vector<int>>& grid) {
        n = grid[0].size();
        m = grid.size();

        for(int i = 0; i < m; i++) {
            if(grid[i][0] == 0) {
                flipRow(i, grid);
            }
        }

        for(int j = 1; j < n; j++) {
            int cnt = 0;
            for(int i = 0; i < m; i++) {
                cnt += grid[i][j];
            }
            if(cnt <= m/2) {
                flipCol(j, grid);
            }
        }

        int ans = 0;
        for(int i = 0; i < m; i++) {
            int num = 0;
            for(int j = 0; j < n; j++) {
                num += grid[i][j] * static_cast<double>(pow(2, n-j-1));
            }
            ans += num;
        }


        return ans;
    }
};