1072. Flip Columns For Maximum Number of Equal Rows

문제 링크

내 코드

아이디어가 없다..

Return the maximum number of rows that have all values equal after some number of flips. $\rightarrow$ 뒤집거나 그대로 놔두었을 때 같은 row의 수 반환하기.

Solution

Approach 1: Brute Force

• 125ms, 74.26MB
• Complexity
  • Let n be the number of rows and m be the number of columns in the matrix.
  • Time Complexity: $O(n^2 \cdot m)$
  • Space Complexity: $O(m)$

class Solution {
public:
    int maxEqualRowsAfterFlips(vector<vector<int>>& matrix) {
        int numCols = matrix[0].size();
        int maxIdenticalRows = 0;

        for (auto& currentRow : matrix) {
            // Create vector to store flipped version of current row
            vector<int> flippedRow(numCols);
            int identicalRowCount = 0;

            // Create flipped version of current row (0->1, 1->0)
            for (int col = 0; col < numCols; col++) {
                flippedRow[col] = 1 - currentRow[col];
            }

            // Check every row against current row and its flipped version
            for (auto& compareRow : matrix) {
                // If row matches either original or flipped pattern, increment
                // counter
                if (compareRow == currentRow || compareRow == flippedRow) {
                    identicalRowCount++;
                }
            }

            maxIdenticalRows = max(maxIdenticalRows, identicalRowCount);
        }

        return maxIdenticalRows;
    }
};

Approach 2: Hash Map

패턴 만들기

+---+---+
| 0 | 1 |
+---+---+
| 1 | 0 |
+---+---+

+---+---+
| T | F |   // T = 0
+---+---+
| T | F |   // T = 1
+---+---+

This means that if we replace each row with a unique pattern that represents it, then identical and even complementary rows will share the same pattern. The below illustration visualizes this concept:

So, our task simplifies to just finding the pattern that shows up the most often. To do this, we’ll go through each row in the matrix, converting it into its pattern string. Then, we’ll use a map called patternFrequency to keep track of how many times each pattern appears. Once we’ve done that, we’ll just look through all the values in the map, find the highest frequency, and return that as our answer.

• 16ms, 74.72MB
• Complexity
  • Let n be the number of rows and m be the number of columns in the matrix.
  • Time Complexity: $O(n \cdot m)$
  • Space Complexity: $O(n \cdot m)$

class Solution {
public:
    int maxEqualRowsAfterFlips(vector<vector<int>>& matrix) {
        // Map to store frequency of each pattern
        unordered_map<string, int> patternFrequency;

        for (auto& currentRow : matrix) {
            string patternBuilder = "";

            // Convert row to pattern relative to its first element
            for (int col = 0; col < currentRow.size(); col++) {
                // 'T' if current element matches first element, 'F' otherwise
                if (currentRow[0] == currentRow[col]) {
                    patternBuilder += "T";
                } else {
                    patternBuilder += "F";
                }
            }

            // Convert pattern to string and update its frequency in map
            patternFrequency[patternBuilder]++;
        }

        // Find the pattern with maximum frequency
        int maxFrequency = 0;
        for (auto& entry : patternFrequency) {
            maxFrequency = max(entry.second, maxFrequency);
        }

        return maxFrequency;
    }
};

추가 설명 - gpt

문제의 핵심:

우리는 각 행의 값을 “열을 뒤집어” 같은 값으로 만들 수 있는 경우를 찾아야 합니다. 이를 효율적으로 풀기 위해, “행의 패턴”을 비교하는 방법을 사용할 겁니다.

예시 1:

입력:

matrix = [
  [0, 1],
  [1, 0]
]

과정:

1. 첫 번째 행 [0, 1]:

   • 이 행에서 첫 번째 값이 0이므로, 다른 값들도 이를 기준으로 “뒤집음 없이” 패턴화합니다.
   • 패턴으로 변환하면 [0, 1] → "01" (첫 번째 값과 같은 값은 0, 다른 값은 1).

2. 두 번째 행 [1, 0]:

   • 이 행에서 첫 번째 값이 1입니다. 따라서 첫 번째 값과 동일한 값을 0, 다른 값을 1로 변환합니다.
   • 패턴으로 변환하면 [1, 0] → "01".

3. 두 행 모두 같은 패턴 "01"을 가집니다. 따라서 이 패턴으로 두 행 모두 “같은 값”으로 만들 수 있습니다.

출력:

2

예시 2:

입력:

matrix = [
  [0, 1, 0],
  [1, 0, 1],
  [0, 0, 0]
]

과정:

1. 첫 번째 행 [0, 1, 0]:

   • 첫 번째 값이 0이므로, 이를 기준으로 변환합니다.
   • 변환된 패턴: [0, 1, 0] → "010".

2. 두 번째 행 [1, 0, 1]:

   • 첫 번째 값이 1이므로, 이를 기준으로 변환합니다.
   • 변환된 패턴: [1, 0, 1] → "010" (첫 번째 값을 기준으로 뒤집으면 같은 패턴).

3. 세 번째 행 [0, 0, 0]:

   • 첫 번째 값이 0이므로, 변환 후 [0, 0, 0] → "000".

4. 패턴 빈도:

   • "010": 2번 등장 (첫 번째, 두 번째 행).
   • "000": 1번 등장 (세 번째 행).

출력:

2

예시 3 (혼자 풀어보세요):

입력:

matrix = [
  [1, 1, 0],
  [0, 0, 1],
  [1, 1, 1]
]

1. 첫번째 행: [1, 1, 0] $\rightarrow$ "110"
2. 두번째 행: [0, 0, 1] $\rightarrow$ "110" (첫 행 기준)
3. 세번재 행: [1, 1, 1] $\rightarrow$ "111" (첫 행 기준)
4. 패턴 빈도:
   • "110": 2번 등장 (첫 번째, 두 번째 행).
   • "111": 1번 등장 (세 번째 행).

출력:

2

핵심 아이디어 정리:

1. 모든 행을 “패턴”으로 변환해서 동일한 패턴을 찾는 문제입니다.
2. 열을 뒤집는 동작은 행 전체의 패턴을 유지하기 때문에, 비교할 때 “뒤집힌 행”도 같은 패턴으로 처리됩니다.
3. 해시맵을 사용해서 패턴 빈도를 기록하면 효율적으로 최대 값을 구할 수 있습니다.

그리고 코드

29ms, 74.58MB

class Solution {
public:
    int maxEqualRowsAfterFlips(std::vector<std::vector<int>>& matrix) {
        std::unordered_map<std::string, int> pattern_count;
        int max_rows = 0;

        for (const auto& row : matrix) {
            std::string pattern;
            for (int val : row) {
                pattern += (val == row[0]) ? '0' : '1';
            }
            max_rows = std::max(max_rows, ++pattern_count[pattern]);
        }

        return max_rows;
    }
};