[코테연습] 1072. Flip Columns For Maximum Number of Equal Rows

https://leetcode.com/problems/flip-columns-for-maximum-number-of-equal-rows/description/?envType=daily-question&envId=2024-11-22

 

 

문제 타입

• 배열 및 행렬 문제: 2차원 행렬에서 열을 뒤집는 작업을 통해 최대한 많은 행을 동일하게 만듦
• 패턴 매칭 문제: 행렬의 특정 패턴(원본 및 반전)을 탐색하고 빈도를 계산
• 해시맵 활용 문제: 중복된 패턴의 빈도를 빠르게 찾기 위해 해시맵 사용

---

문제 분석

• 입력
  • matrix: n x m 크기의 2차원 배열. 각 요소는 0 또는 1
• 작업
  • 특정 열을 뒤집는 연산(0은 1로, 1은 0으로)을 수행 가능
  • 열을 몇 번 뒤집든, 행렬 내에서 동일한 행이 최대 몇 개가 될 수 있는지 계산
• 제약
  • 각 행은 고유하거나 반전된 형태를 가질 수 있음
  • 행이 동일하게 되려면:
    1. 모든 열 값이 동일하거나
    2. 열 값이 서로 반전된 형태여야 함
• 출력
  • 동일한 행의 최대 개수

---

문제 풀이

1. 패턴 정의 및 빈도 계산

• 행이 동일한 행이 되려면:
  • 그 자체로 같은 행(원본 패턴)이어야 하거나
  • 모든 열이 뒤집힌 경우와 동일해야 함(반전된 패턴)
• 각 행을 원본 패턴과 반전 패턴으로 표현하고 이를 해시맵에 저장

2. 알고리즘

• 행렬 탐색
  1. 각 행을 순회하며 원본 패턴과 반전 패턴 생성
  2. 해시맵에 패턴을 키로 저장하고, 빈도를 업데이트
• 최댓값 계산
  • 해시맵의 값들 중 가장 큰 값을 반환

3. 구현

• 해시맵에 각 패턴(원본 및 반전)의 등장 횟수를 저장
• 모든 패턴의 빈도 중 최댓값을 결과로 반환

4. 시간 및 공간 복잡도

• 시간 복잡도: O(n x m)
  • n: 행 개수, m: 열 개수
  • 각 행을 순회하며 패턴 생성 및 해시맵 업데이트
• 공간 복잡도: O(n)
  • 해시맵에 패턴 저장

 

> java

 

class Solution {
    public int maxEqualRowsAfterFlips(int[][] matrix) {
        // 해시맵을 사용하여 각 행의 패턴(원본과 반전)을 카운트
        Map<String, Integer> map = new HashMap<>();
        
        // 행렬의 각 행을 순회
        for (int[] row : matrix) {
            // 현재 행의 원본 패턴을 저장할 StringBuilder
            StringBuilder origin = new StringBuilder();
            // 현재 행의 반전된 패턴을 저장할 StringBuilder
            StringBuilder flipped = new StringBuilder();
            
            // 행의 각 열을 순회
            for (int col : row) {
                // 원본 값 추가
                origin.append(col);
                // 반전된 값 추가 (0 -> 1, 1 -> 0)
                flipped.append(col ^ 1);
            }
            
            // 원본 패턴과 반전 패턴을 문자열로 변환
            String originPattern = origin.toString();
            String flippedPattern = flipped.toString();
            
            // 원본 패턴과 반전 패턴의 카운트를 증가
            map.put(originPattern, map.getOrDefault(originPattern, 0) + 1);
            map.put(flippedPattern, map.getOrDefault(flippedPattern, 0) + 1);
        }
        
        // 최대 동일 행 개수를 계산
        int max = 0;
        for (int count : map.values()) {
            // 각 패턴의 카운트 중 최댓값을 구함
            max = Math.max(count, max);
        }
        
        // 최댓값 반환
        return max;
    }
}

 

> python

 

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        # 딕셔너리를 사용하여 각 패턴의 빈도를 저장
        map = {}

        # 행렬의 각 행을 순회
        for row in matrix:
            # 원본 패턴을 저장할 문자열
            originPattern = ''
            # 반전된 패턴을 저장할 문자열
            flippedPattern = ''
            
            # 현재 행의 각 열을 순회
            for col in row:
                # 원본 패턴에 현재 값 추가
                originPattern += str(col)
                # 반전된 패턴에 XOR 연산으로 반전된 값 추가 (0 -> 1, 1 -> 0)
                flippedPattern += str(col ^ 1)
            
            # 원본 패턴의 빈도 증가
            map[originPattern] = map.get(originPattern, 0) + 1
            # 반전된 패턴의 빈도 증가
            map[flippedPattern] = map.get(flippedPattern, 0) + 1

        # 딕셔너리에서 가장 높은 패턴 빈도를 반환
        return max(map.values())