[LeetCode] 554. Brick Wall

😎풀이

1. 각 줄에서 접두사 합계를 구하며, 최 다 빈두의 접두사 합계 계산
2. 이 때, 마지막 길이는 취급하지 않음 문제에 정의된 바와 같이 양 끝은 취급하지 않기 때문
3. 전체 줄에서 가장 많은 여백이 생기는 줄(접두사 합계가 같은 줄)의 수를 차감한 값 반환

function leastBricks(wall: number[][]): number {
    const n = wall.length
    const prefixSumFreq = new Map<number, number>()
    let maxFreq = 0
    for(const row of wall) {
        let prefixSum = 0
        for(let i = 0; i < row.length - 1; i++) {
            prefixSum += row[i]
            const curFreq = (prefixSumFreq.get(prefixSum) ?? 0) + 1
            prefixSumFreq.set(prefixSum, curFreq)
            maxFreq = Math.max(maxFreq, curFreq)
        }
    }
    return n - maxFreq
};