[2024] day 135. Leetcode 861. Score After Flipping Matrix

gunny·2024년 5월 13일

leetcode 861. Score After Flipping Matrix leetcode 861. Score After Flipping Matrix python

코딩테스트

목록 보기

449/530

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 5월 13일 (월)
Leetcode daily problem

861. Score After Flipping Matrix

https://leetcode.com/problems/minimum-cost-to-hire-k-workers/?envType=daily-question&envId=2024-05-11

Problem

이진 행렬이 주어졌을 때, 특정 조건에 따라 이진 행렬의 값을 조작하여 최대 점수를 얻는 문제이다.

m x n 이진 행렬 그리드가 제공될 때,
행이나 열을 선택하고 해당 행이나 열의 각 값을 전환하면서 이동할 수 있다. 즉, 주어진 이진 행렬에서 한 행의 모든 요소를 뒤집어서 0은 1로, 1은 0으로 바꿀 수 있고, 한 열의 모든 요소를 뒤닙어서 마찬가지로 0은 1로, 1은 0으로 바꿀 수 있다.

Solution

Greedy, bit operation

해당 문제에서는 행렬의 각 행의 합을 최대화해야 하므로, 각 행의 정수 값이 최대가 되도록 하는 것이 중요하다.

이진수에서 높은 자리수의 비트가 작은 자리수의 비트보다 더 큰 가중치를 가지기 때문에, 첫 번째 열의 모든 비트가 1이 되도록 최대화하는 것이 좋다. 그렇기 때문에 각 행의 첫 번째 비트를 1로 만들어 주는 작업을 먼저하게 된다.

그 다음으로는 열의 최적화에 초점을 맞춘다. 열의 기여도는 그 열에 있는 1의 개수에만 의존하기 때문에, 각 열에 있는 1의 개수를 최대화하는 것이 이상적이다. 따라서 열을 최적화하기 위해서는 열의 1보다 0이 더 많으면 열을 뒤집어야 한다.

마지막으로는 각 행의 정수 값을 계산하여 행렬의 점수를 계산한다. 각 비트의 기여도는 해당 비트의 위치에 따라 결정되는데, 이는 비트를 해당 위치만큼 왼쪽으로 이동시키면 된다.

요약하자면, 이 문제를 해결하기 위한 핵심 단계는 행렬의 첫 번째 열의 모든 요소가 1이 되도록 행을 뒤집는다. 그리고, 열의 1보다 0이 더 많은 경우에만 열을 뒤집는다.

Code

class Solution:
    def matrixScore(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        for i in range(m):
            if grid[i][0] == 0:
                for j in range(n):
                    grid[i][j] = 1-grid[i][j]
                    
        for j in range(n):
            zero_cnt = 0
            for i in range(m):
                if grid[i][j]==0:
                    zero_cnt +=1
            
            if zero_cnt > m-zero_cnt:
                for i in range(m):
                    grid[i][j] ^=1
                    
        score = 0
        for i in range(m):
            for j in range(n):
                colScore= grid[i][j] << (n-j-1)
                score += colScore
                
        return score