[Leetcode 1072번 문제] 1072. Flip Columns For Maximum Number of Equal Rows

문제 상황

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 * n의 매트릭스가 있고, 몇개의 열들이 있고, 한 열의 모든 요소들을 뒤집을 수도 있다. 최대의 number of rows를 구해라.

all values equal after some number of flips 플립을 구할건데. 각 row가 모두 동일한 요소일때 최대의 row를 구해라.

입력

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

출력

정수

과정

오히려 모든 row를 기준으로 &를

전부 1로 바뀌는 상황이거나 전부 0으로 바뀌는 놈들이 있으면 되니까 일단 기본 생각은

1. 각 row에 대해서 전부 1로 바뀌거나 또는 0으로 바꾸기 위해서 건들여야하는 column 배열을 설정해 놓는다.
2. 각 배열들에 대해서 자기랑 정확히 일치하는 값을 모두 구한다.
3. 그중에서 제일 큰 놈을 그냥 골라서 넣는다.

알고리즘 개요도

알고리즘

class Solution {
public:
    int maxEqualRowsAfterFlips(vector<vector<int>>& matrix) {
        int Tsize = matrix.size();
        int Csize = matrix[0].size();
        vector<vector<int>> flips (Tsize * 2, vector<int>{});
        int answer = 0;
        for (int i = 0; i < Tsize; i++)
        {
            for (int j = 0; j < Csize; j++)
            {
                if (matrix[i][j] == 0)
                {
                    flips[i].push_back(j);
                }
                else
                {
                    flips[i + Tsize].push_back(j);
                }
            }
            if (flips[i].size() == 0 || flips[i + Tsize].size() == 0)
            {
                answer++;
            }
        }

        for (int i = 0; i < Tsize * 2; i++)
        {
            int tmp = 1;
            for (int j = 0; j < Tsize * 2; j++)
            {
                // cout << '\\t' << i  << ' ' << j  << '\\n';
                if ((i % Tsize) == (j % Tsize) || (flips[i].size() != flips[j].size()) )
                    continue;
                
                bool isSame = true;
                for (int k = 0; k < flips[i].size(); k++)
                {
                    // cout << flips[i][k] << ' ' << flips[j][k] << '\\n';
                    if (flips[i][k] != flips[j][k])
                    {
                        isSame = false;
                        break;
                    }
                }
                if (!isSame)
                    continue;
                tmp++;
            }
            answer = max(answer, tmp);
        }
        return answer;

    }
};