1. 문제 소개

474. Ones and Zeroes

2. 나의 풀이

처음 보았을 때에는 바로 감을 잡지 못했다.
Dynamic Programming을 사용하여 풀 수 있다는 힌트를 보고 고민을 해봤다.
각각의 이진숫자에 대해서 0과 1을 dp에 저장해가며 풀었다.
중요한 점은 dp를 채울 때에 역순으로 조회해가며 값을 채워야한다는 점인데, 현재 이진숫자를 적용하기 이전의 상태를 반영해야하기 때문이다.
따라서 한 문자열이 정확히 한 번만 반영된다.
시간복잡도는 $O(len(strs) × m × n)$이다.

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dp = [[0] * (n + 1) for _ in range(m + 1)]  # dp[i][j]: i개의 0, j개의 1로 만들 수 있는 최대 문자열 개수

        for s in strs:                               # 각 문자열을 하나의 아이템으로 생각
            zeros, ones = s.count("0"), s.count("1") # 소비되는 0,1의 개수 계산
            for i in range(m, zeros - 1, -1):        # 역순: 같은 문자열 중복 방지 (0/1 배낭 표준)
                for j in range(n, ones - 1, -1):
                    dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)
                    # 선택 안함: dp[i][j]
                    # 선택함: dp[i - zeros][j - ones] + 1 (현재 문자열 추가)
        
        return dp[m][n]                              # 최대 m개의 0, n개의 1로 만들 수 있는 최대 문자열 개수

3. 다른 풀이

다른 풀이의 경우 해시맵을 사용한 dp(HashMap DP)로 풀었다.
필요한 상태만 저장하는 해시맵 dp는 가능한 조합만 기억하는 똑똑한 방법을 사용한다.

strs = ["10", "0001", "111001", "1", "0"]
m=5, n=3

1. 시작: {(0,0):0}
2. "10" 처리
   • (0,0) + (1,1) → (1,1): 1개
     → dp = {(0,0):0, (1,1):1}
3. "0001" 처리
   • (0,0) → (3,1):1
   • (1,1) → (4,2):2
     → dp = {(0,0):0, (1,1):1, (3,1):1, (4,2):2}
4. 나머지 문자열 반복
   → 최종적으로 5개의 0과 3개의 1로 4개 문자열 가능.

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dp = {(0, 0): 0}

        for s in strs:
            ones = s.count('1')
            zeroes = s.count('0')
            newdp = {}

            for (prevZeroes, prevOnes), val in dp.items():
                newZeroes, newOnes = prevZeroes + zeroes, prevOnes + ones
                if newZeroes <= m and newOnes <= n:
                    if (newZeroes, newOnes) not in dp or dp[(newZeroes, newOnes)] < val + 1:
                        newdp[(newZeroes, newOnes)] = val + 1

            dp.update(newdp)

        return max(dp.values())

4. 결론

생각지 못한 해시맵 dp를 알게 되어 기분이 좋다.