[LeetCode] 474. Ones and Zeroes

😎풀이

1. m과 n을 담을 수 있는 2차원 DP 배열 생성 후 0으로 초기화
2. strs 순회
   2-1. 현재 문자의 Binary 빈도 파악
   2-2. m과 n으로 부터 역방향으로 현재 바이너리를 포함하여 만들 수 있는 최대 서브셋의 수 누적
   2-3. 0을 5개, 1을 3개 사용해서 만들 수 있는 바이너리는 01, 11, ...
3. 0을 m개, 1을 n개 사용하여 만들 수 있는 최대 서브셋의 수 반환

function findMaxForm(strs: string[], m: number, n: number): number {
    const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0))
    for(const str of strs) {
        const [zero, one] = [...str].reduce((acc, cur) => {
            if(cur === '1') return [acc[0], acc[1] + 1]
            return [acc[0] + 1, acc[1]]
        }, [0, 0])
        for(let i = m; i >= zero; i--) {
            for(let j = n; j >= one; j--) {
                dp[i][j] = Math.max(dp[i][j], dp[i - zero][j - one] + 1)
            }
        }
    }
    return dp[m][n]
};