이 글에서는 자바스크립트(JavaScript)로 시퀀스 배열에서 값 그룹을 제거할 수 있는 모든 가능한 방법의 개수를 구하는 방법을 알아봅니다.
문제 이해하기
요구 사항은 다음과 같습니다. 원본 시퀀스에서 제거하려는 값 그룹을 뽑아낼 때, 원본 배열의 요소 순서는 반드시 유지되어야 하며(안정성 보장), 각 값은 원본에서 단 한 번씩만 제거해야 합니다. 이 조건을 만족하는 서로 다른 제거 방법이 총 몇 가지인지 반환하는 함수를 작성하는 것입니다.
예제
예를 들어 원본 시퀀스 배열이 다음과 같다고 가정해 보겠습니다.
const arr = [1, 2, 1, 3, 1, 4, 4];
그리고 제거해야 할 배열이 다음과 같습니다.
const arr2 = [1, 4, 4];
이 경우 요소들의 순서를 깨지 않으면서 값을 제거할 수 있는 방법은 세 가지입니다.
1 --> [2, 1, 3, 1]
2 --> [1, 2, 3, 1]
3 --> [1, 2, 1, 3]
따라서 위 두 배열이 입력으로 주어졌을 때 우리 함수는 3을 출력해야 합니다.
코드 구현
const arr = [1, 2, 1, 3, 1, 4, 4];
const arr2 = [1, 4, 4];
const possibleRemovalCombinations = (original, part) => {
const sorter = (a, b) => a - b;
part.sort(sorter);
let place = [];
part.forEach(el => {
place[el] = []
});
original.forEach((el, index) => {
if(place[el]){
place[el].push(index);
}
});
let connection = part.map(el => place[el].slice());
for(let i = 1; i < connection.length; i++){
if (part[i - 1] != part[i]){
continue;
}
let left = connection[i - 1][0];
while(connection[i][0] <= left){
connection[i].shift();
};
};
for (let i = connection.length - 2; i >= 0; i--) {
if(part[i] != part[i + 1]){
continue;
}
let right = connection[i + 1][connection[i + 1].length - 1];
while(connection[i][connection[i].length - 1] >= right){
connection[i].pop();
};
};
const combineArray = (step, prev, combination) => {
for (let i = 0; i < connection[step].length; i++) {
let curr = connection[step][i];
if(prev >= curr && original[prev] == original[curr]){
continue;
}
if(step + 1 == connection.length){
combinations.push(combination.concat([curr]))
}
else {
combineArray(step + 1, curr, combination.concat([curr]));
};
};
};
let combinations = [], res = [];
combineArray(0, -1, []);
for (let i = 0; i < combinations.length; i++) {
let copy = original.slice();
combinations[i].forEach(el => copy[el]);
res[i] = copy.filter(el => el !== undefined);
};
return res.length;
};
console.log(possibleRemovalCombinations(arr, arr2));
동작 원리
위 코드의 핵심 로직을 단계별로 살펴보면 다음과 같습니다.
- 정렬: 먼저 제거 대상 배열(part)을 오름차순으로 정렬하여 같은 값들이 연속으로 배치되도록 합니다.
- 인덱스 매핑: 원본 배열을 순회하면서 제거 대상 값이 등장하는 모든 인덱스를 값별로 기록합니다.
- 경계 정리: 제거 배열에서 연속된 같은 값에 대해서는 선택되는 인덱스가 항상 왼쪽에서 오른쪽으로 증가하도록 앞쪽(shift)과 뒤쪽(pop) 경계를 잘라냅니다.
- 조합 생성: 재귀 함수(combineArray)를 통해 유효한 인덱스 조합을 모두 탐색하고, 각 조합에 대해 실제 제거 후의 배열을 만들어 개수를 셉니다.
출력 결과
콘솔에 출력되는 결과는 다음과 같습니다.
3
이처럼 인덱스 기반 접근 방식을 사용하면 중복 조합을 효율적으로 걸러내면서, 순서가 유지된 상태에서 값 그룹을 제거할 수 있는 모든 경우의 수를 정확하게 계산할 수 있습니다.