554. Brick Wall

문제 링크 : https://leetcode.com/problems/brick-wall/description/

가장 최소한의 벽돌이 깨지는 벽돌의 수를 반환하는 문제이다.

벽들의 길이와 gap을 해시함수에 저장하고
전체 wall의 개수에서 갭의 개수를 빼야한다.
(그림과 같이 이해해야 풀기가 수월할 듯)

class Solution:
    def leastBricks(self, wall: List[List[int]]) -> int:
        hmap = defaultdict(int) #width : gap
        width = 0
    
        for i in wall:
            for j in accumulate(i[:-1]):
                hmap[j] += 1
                width = max(width, hmap[j])

        return len(wall) - width