0과 1로만 구성된 문자열 배열이 주어졌을 때, 제한된 개수의 0과 1만 사용해서 만들 수 있는 문자열의 최대 개수를 구하는 문제는 코딩 테스트에 자주 등장하는 동적 계획법(DP) 유형입니다. 이번 글에서는 JavaScript로 이 문제를 해결하는 방법을 단계별로 살펴보겠습니다.
문제 정의
첫 번째 인수로는 0과 1로만 이루어진 문자열 배열 arr을, 두 번째와 세 번째 인수로는 숫자 m과 n을 각각 받는 JavaScript 함수를 작성해야 합니다.
함수의 목표는 배열에 있는 문자열 중에서 0을 최대 m개, 1을 최대 n개까지만 사용하여 선택할 수 있는 문자열의 최대 개수를 반환하는 것입니다.
입력 및 출력 예시
예를 들어 함수에 다음과 같이 입력값을 전달한다고 가정해 보겠습니다.
const arr = ["10", "0001", "111001", "1", "0"]; const m = 5, n = 3;
이 경우 기대되는 출력값은 다음과 같습니다.
const output = 4;
결과 설명
0을 5개, 1을 3개 사용하여 만들 수 있는 문자열은 다음과 같이 총 4개입니다.
"10", "0001", "1", "0"
반면 "111001"은 1이 4개나 필요하기 때문에 n = 3이라는 제한을 초과하여 선택할 수 없습니다.
풀이 코드
이 문제는 각 문자열을 아이템으로, 사용 가능한 0과 1의 개수를 배낭의 용량으로 보는 2차원 배낭(Knapsack) 문제로 볼 수 있습니다. 먼저 각 문자열에 포함된 0과 1의 개수를 계산한 뒤, 2차원 DP 테이블을 역순으로 갱신하며 최댓값을 누적하는 방식으로 해결할 수 있습니다.
const arr = ["10", "0001", "111001", "1", "0"];
const m = 5, n = 3;
const findAllStrings = (arr = [], m = 1, n = 1) => {
const getCount = str => str.split('').reduce((acc, cur) => {
cur === '0' ? acc.zeros++ : acc.ones++;
return acc;
}, {zeros: 0, ones: 0});
const dp = Array.from({length: m + 1}, () => Array(n + 1).fill(0));
for (let i = 0; i < arr.length; i++) {
const {zeros, ones} = getCount(arr[i]);
for (let j = m; j >= zeros; j--) {
for (let k = n; k >= ones; k--) {
dp[j][k] = Math.max(dp[j - zeros][k - ones] + 1, dp[j][k]);
}
}
}
return dp[m][n];
};
console.log(findAllStrings(arr, m, n));
코드 동작 원리
1단계 — 문자열 분석: getCount 헬퍼 함수는 각 문자열을 순회하며 0과 1의 개수를 각각 세어 객체 형태로 반환합니다.
2단계 — DP 테이블 초기화: 크기가 (m+1) × (n+1)인 2차원 배열을 생성하고 모든 값을 0으로 채웁니다. dp[j][k]는 0을 j개, 1을 k개까지 사용할 때 만들 수 있는 문자열의 최대 개수를 의미합니다.
3단계 — 상태 갱신: 각 문자열에 대해 필요한 0과 1의 개수만큼 여유가 있을 때, 해당 문자열을 선택하는 경우(dp[j - zeros][k - ones] + 1)와 선택하지 않는 경우(dp[j][k]) 중 더 큰 값으로 테이블을 갱신합니다. 인덱스를 역순으로 순회하기 때문에 같은 문자열이 중복으로 선택되는 일은 발생하지 않습니다.
실행 결과
위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.
4
마무리
이 문제의 핵심은 각 문자열을 '선택한다 / 선택하지 않는다' 두 가지 경우로 나누어 더 큰 값을 DP 테이블에 저장하는 것입니다. 시간 복잡도는 O(L × m × n)(L은 문자열 배열의 길이), 공간 복잡도는 O(m × n)입니다. 배낭 문제의 변형으로 2차원 비용을 다루는 DP 패턴을 익히는 데 매우 좋은 예제이니, 역순 갱신의 원리까지 함께 기억해 두시기 바랍니다.