다음과 같은 이진 배열(배열 A)이 있다고 가정해 보겠습니다.
const arr = [1,0,1,1,1,1,0,1,1];
이 배열을 sumRight()와 같은 함수에 전달하면 아래와 같은 출력 배열(배열 B)이 생성됩니다.
const output = [1,0,4,3,2,1,0,2,1];
함수의 동작 원리
배열 arr의 요소는 0 또는 1만 가질 수 있습니다. 이 함수는 배열의 마지막 요소부터 거꾸로 거슬러 올라가며 연속된 1의 개수를 셉니다. 규칙은 다음과 같습니다.
- 배열 arr에서 1이 연속해서 나타나면, 출력 배열의 해당 위치에는 첫 번째 1일 때 1, 두 번째 연속된 1에는 2, 세 번째에는 3이 기록됩니다.
- 입력 배열에서 0이 나오면 출력 배열에도 그대로 0이 들어가며, 연속 카운트는 초기화됩니다.
즉, 각 위치에서 "그 위치를 포함해 오른쪽 방향으로 연속된 1이 몇 개인지"를 기록하는 것이 핵심입니다. 예를 들어 인덱스 2~5의 값 [1,1,1,1]은 오른쪽에서부터 각각 4, 3, 2, 1로 변환됩니다.
reduceRight()를 활용한 구현
Array.prototype.reduceRight() 메서드를 사용하면 이 로직을 깔끔하게 구현할 수 있습니다. reduceRight()는 일반적인 reduce()와 동일한 작업을 수행하지만, 왼쪽이 아닌 오른쪽(배열의 끝)부터 순회한다는 점이 다릅니다.
예제 코드
const arr = [1,0,1,1,1,1,0,1,1];
const sumRight = arr => {
return arr.reduceRight((acc, val) => {
const { prev, res } = acc;
if(val === 0){
return {
prev: 0,
res: res.concat(0)
};
}
return {
res: res.concat(val+prev),
prev: prev+1
};
}, {
prev: 0,
res: []
}).res.reverse();
};
console.log(sumRight(arr));
코드 설명
- acc(누산기): prev(현재까지 연속된 1의 개수)와 res(결과 배열) 두 속성을 유지합니다.
- 요소가 0이면 prev를 0으로 초기화하고 결과 배열에 0을 추가합니다.
- 요소가 1이면 val + prev 값을 결과에 추가하고 prev를 1 증가시킵니다.
- reduceRight()는 오른쪽부터 순회하므로 결과 배열이 역순으로 쌓이게 되고, 마지막에 reverse()로 원래 순서를 복원합니다.
실행 결과
콘솔에 출력되는 결과는 다음과 같습니다.
[
1, 0, 4, 3, 2,
1, 0, 2, 1
]
더 효율적인 대안: 단순 반복문
위 코드는 매 단계마다 concat()으로 새 배열을 생성하기 때문에 배열이 클 경우 성능이 저하될 수 있습니다. 단순한 for 반복문을 사용하면 O(n) 시간 복잡도로 더 효율적으로 처리할 수 있습니다.
const sumRight = arr => {
const res = new Array(arr.length);
let count = 0;
for (let i = arr.length - 1; i >= 0; i--) {
count = arr[i] === 0 ? 0 : count + 1;
res[i] = count;
}
return res;
};
console.log(sumRight(arr)); // [1, 0, 4, 3, 2, 1, 0, 2, 1]두 방식 모두 동일한 결과를 반환하지만, 대용량 데이터를 다룰 때는 반복문 방식이 메모리 할당과 실행 시간 면에서 유리합니다.