[LeetCode] 474 | Ones and Zeros | Python

---

문제 링크: https://leetcode.com/problems/ones-and-zeroes/

---

문제

You are given an array of binary strings strs and two integers m and n.

Return the size of the largest subset of strs such that there are at most m 0's and n 1's in the subset.

A set x is a subset of a set y if all elements of x are also elements of y.

---

조건

• 1 <= strs.length <= 600
• 1 <= strs[i].length <= 100
• strs[i] consists only of digits '0' and '1'.
• 1 <= m, n <= 100

---

내 풀이

DP로 해결한다.

count에는 각 str의 0과 1의 개수를 저장한다.

 

어떤 str에 0과 1이 각각 zeros, ones만큼 있다고 할 때, 현재 str을 subset에 포함시킨다면 dp[zeros][ones]부터 dp[m][n]까지 경우의 수가 하나 증가한다. 이것을 dp로 짠다.

다만 for문의 범위를 (m, zeros-1, -1)과 같이 역순으로 제공했는데, 그 이유는 역순으로 하지 않으면 중복되는 경우가 생기기 때문이다.

---

코드

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
        count = [[s.count('0'), s.count('1')] for s in strs]
        
        for zeros, ones in count:
            for i in range(m, zeros-1, -1):
                for j in range(n, ones-1, -1):
                    dp[i][j] = max(dp[i][j], 1+dp[i-zeros][j-ones])
        
        return dp[-1][-1]