[LeetCode] 1072. Flip Columns For Maximum Number of Equal Rows

https://leetcode.com/problems/flip-columns-for-maximum-number-of-equal-rows/description/

leetcode - Flip Columns For Maximum Number of Equal Rows

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

문제 난이도: Medium

 

문제

You are given an m x n binary matrix matrix.

You can choose any number of columns in the matrix and flip every cell in that column (i.e., Change the value of the cell from 0 to 1 or vice versa).

Return the maximum number of rows that have all values equal after some number of flips.

 

m x n의 이진 행렬 matrix가 주어진다.

열을 골라서 그 열을 비트플립 시킬 수 있다.

몇 번이고 할 수 있다.

행의 비트가 모두 같은 rows의 최대 개수를 구하시오.

 

풀이

열 하나를 플립하면, 의도치 않게 다른 행들에게도 영향을 받게 된다.

그러나 어느 열을 뒤집든, 서로 영향주지 않는 관계가 있다.

자신과 값이 똑같은 행 또는, 비트가 보수 관계인 행이다.

이 관계에 있으면 어떻게 뒤집던간에 일관된 패턴을 가진다.

 

즉, 같은 패턴이거나 보수 패턴인 열들을 그룹화하여 가장 많은 개수를 리턴하면 된다.

그 그룹을 중심으로 비트플립을 진행하면 같은 패턴들은 000000...0, 보수 패턴들은 111111..1이 될 것이다.

 

해시맵으로 비트문자열-개수를 저장할 것이고,

행의 각 열들을 읽으면서, 비트문자열을 만들어 개수를 누적해서 그룹원의 개수를 추적한다.

시작 비트가 0이느냐 1이느냐에 따라 다르겠지만, 0이면 그냥 그대로 세고, 1이면 모든 비트를 플립해서  보수 비트열을 만들어서 '0'으로 시작하는 같은 그룹으로 묶이도록 한다.

 

코드

C++

class Solution {
public:
    int maxEqualRowsAfterFlips(vector<vector<int>>& matrix) {
        unordered_map<string, int> count;

        for(const auto &row : matrix) {
            string key;
            bool flip = row[0] == 1;

            for(int num : row) {
                key += flip ? ('0' + (1-num)) : ('0' + num);
            }

            count[key]++;
        }
        int maxCount = 0;
        for(const auto &pair : count) {
            maxCount = max(maxCount, pair.second);
        }

        return maxCount;
    }
};