861. Score After Flipping Matrix

Problem : https://leetcode.com/problems/score-after-flipping-matrix/

 

Difficulty : Medium

 

Status : Solved

 

Time : ??:??:??

 

---

 

문제 설명

 

---

 

풀이

 

비트마스킹은 너무 느렸다...! 좀 더 간결히, 그리고 문제의 본질을 꿰뚫어야 풀 수 있는 문제였다.

 

언뜻 보면 모든 경우의 수를 다 테스트해보아야 할 것 같지만, 함정이 있다. score는 이진법으로 계산되므로, 제일 높은 차수(0번째 column)가 모두 1인 경우가 그리디하게 가장 큰 값을 지니게 된다. 즉 column 0을 1로 세팅하도록 하자.

 

이제 column 1부터 순회를 시작하면 된다. 이 때, column 0이 원래 1인 경우는 row가 뒤집어진 경우이므로 뒤집어 준 후, 이 column의 총 1의 개수를 세어주도록 하자. 여기서도 그리디하게, (현재 1의 개수) 와 (현재 0의 개수) 중 더 큰 쪽이 1이 되도록 택하면 가장 큰 값을 지니게 된다. 모든 column에 대하여 이를 반복하면 최종적으로 빠르게 값을 구할 수 있다.

 

 

풀이 코드 (Python)

class Solution:
    def matrixScore(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        result = m * (1 << (n - 1))
        for i in range(1, n) :
            tmp = 0
            for j in range(m) :
                if grid[j][0] == 0 :
                    grid[j][i] = 1 - grid[j][i]
                if grid[j][i] == 1 :
                    tmp += 1
            result += (1 << (n - i - 1)) * max(tmp, m - tmp)
        return result

 

 

풀이 코드 (Go)

func matrixScore(grid [][]int) int {
    m := len(grid)
    n := len(grid[0])
    result := (1 << (n - 1)) * m
    for i := 1; i < n; i++ {
        tmp := 0
        for j := 0; j < m; j++ {
            if grid[j][0] == 0 {
                grid[j][i] = 1 - grid[j][i]
            }
            if grid[j][i] == 1 {
                tmp += 1
            }
        }
        if tmp < m - tmp {
            tmp = m - tmp
        }
        result += (1 << (n - i - 1 )) * tmp
    }
    return result
}