문제 설명
각 문자열이 문자 "A"와 "B"로만 구성된 문자열 리스트가 있다고 가정해 보겠습니다. 두 정수 a와 b가 주어질 때, 만들 수 있는 문자열의 최대 개수를 구하는 것이 목표입니다. 각 문자열은 한 번만 선택할 수 있으며, 전체적으로 사용되는 "A"는 최대 a개, "B"는 최대 b개로 제한됩니다.
예를 들어 입력이 strings = ["AAABB", "AABB", "AA", "BB"], a = 4, b = 2라면 출력은 2가 됩니다. 4개의 "A"와 2개의 "B"를 사용해 ["AABB", "AA"] 두 문자열을 선택할 수 있기 때문입니다.
접근 방법
이 문제는 잘 알려진 0/1 배낭(Knapsack) 문제의 변형입니다. 각 문자열은 비용이 ("A" 개수, "B" 개수)이고 가치가 1인 아이템이며, 예산은 a개의 "A"와 b개의 "B"입니다. 따라서 예산 범위 안에서 선택한 아이템 수를 최대화하면 됩니다.
이를 해결하기 위해 딕셔너리 기반 동적 계획법(DP)을 사용하며, 단계는 다음과 같습니다.
- pairs라는 새로운 리스트를 생성합니다.
- strings의 각 문자열 w에 대해 다음을 수행합니다.
- A := w에 포함된 "A"의 개수
- B := len(w) - A ("B"의 개수)
- pairs 끝에 쌍 (A, B)를 추가합니다.
- ans := {(a, b): 0} 형태의 맵을 생성합니다. 키는 남은 "A"/"B" 예산 상태, 값은 해당 상태까지 선택한 문자열 수입니다.
- pairs의 각 쌍 (A, B)에 대해 다음을 수행합니다.
- temp := ans를 복사한 새로운 맵
- ans의 각 상태 (temp_a, temp_b)와 값 wc에 대해:
- temp_a >= A이고 temp_b >= B라면(선택할 여유가 있다면):
- rem := (temp_a - A, temp_b - B)
- temp[rem] := max(temp.get(rem, 0), wc + 1)
- temp_a >= A이고 temp_b >= B라면(선택할 여유가 있다면):
- ans := temp
- ans의 모든 값 중 최댓값을 반환합니다.
구현 예시
class Solution:
def solve(self, strings, a, b):
pairs = []
for w in strings:
A = w.count("A")
B = len(w) - A
pairs.append((A, B))
ans = {(a, b): 0}
for A, B in pairs:
temp = dict(ans)
for (temp_a, temp_b), wc in ans.items():
if temp_a >= A and temp_b >= B:
rem = (temp_a - A, temp_b - B)
temp[rem] = max(temp.get(rem, 0), wc + 1)
ans = temp
return max(ans.values())
ob = Solution()
strings = ["AAABB", "AABB", "AA", "BB"]
a = 4
b = 2
print(ob.solve(strings, a, b))입력
["AAABB", "AABB", "AA", "BB"], 4, 2
출력
2
동작 원리 살펴보기
초기 상태는 남은 예산 (4, 2)에서 문자열을 0개 선택한 것입니다. 첫 번째 문자열 "AAABB"(A=3, B=2)를 처리하면 (4, 2) → (1, 0)으로 이동하는 상태가 추가되고 값은 1이 됩니다. 이후 문자열들을 순회하면서 각 상태에서 선택 가능한 경우마다 새로운 상태를 만들고, 같은 상태에 도달하는 경로 중 선택한 문자열 수가 가장 많은 것을 유지합니다. 마지막에 모든 상태의 최댓값을 반환하므로, 위 예시에서는 ["AABB", "AA"]를 선택한 2가 결과로 나옵니다.
상태의 키는 남은 예산이므로 상태 수는 최대 (a+1)×(b+1)로 제한됩니다. 따라서 시간 복잡도는 대략 O(n × (a+1) × (b+1))이며, 공간 복잡도도 이에 비례합니다. n은 문자열 리스트의 길이입니다.