문제 정의
정수 배열 arr를 첫 번째이자 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다.
이 함수는 배열에서 특정 인덱스 하나를 골라 반환해야 하며, 조건은 다음과 같습니다. 해당 인덱스를 기준으로 왼쪽에 있는 요소들의 합과 오른쪽에 있는 요소들의 합이 서로 같아야 합니다. 만약 그러한 인덱스가 존재하지 않는다면 -1을 반환해야 합니다.
입력 및 출력 예시
예를 들어 함수에 다음과 같은 입력이 주어졌다고 가정해 보겠습니다.
입력
const arr = [1, 2, 3, 4, 3, 2, 1];
출력
const output = 3;
출력 설명
인덱스 3(값 4)을 기준으로 왼쪽 요소들의 합은 1 + 2 + 3 = 6, 오른쪽 요소들의 합은 3 + 2 + 1 = 6으로 양쪽 합계가 동일하기 때문입니다.
기본 풀이: 슬라이싱과 reduce 활용
가장 직관적인 방법은 각 인덱스마다 왼쪽 부분 배열과 오른쪽 부분 배열의 합을 각각 계산하여 비교하는 것입니다.
const arr = [1, 2, 3, 4, 3, 2, 1];
const balancingIndex = (arr = []) => {
// 배열 요소들의 합을 구하는 헬퍼 함수
const findSum = arr => arr.reduce((acc, x) => acc + x, 0);
for (let i = 0; i < arr.length; i++) {
const leftSum = findSum(arr.slice(0, i)); // i 왼쪽 요소들의 합
const rightSum = findSum(arr.slice(i + 1)); // i 오른쪽 요소들의 합
if (leftSum === rightSum) {
return i;
}
}
// 균형 인덱스가 존재하지 않는 경우
return -1;
};
console.log(balancingIndex(arr));출력 결과
3
동작 원리
1. findSum은 reduce()를 사용해 배열의 모든 요소를 더하는 유틸리티 함수입니다.
2. 반복문을 돌며 각 인덱스 i에 대해 slice(0, i)로 왼쪽 부분 배열을, slice(i + 1)로 오른쪽 부분 배열을 추출합니다.
3. 두 합이 일치하는 순간 해당 인덱스를 즉시 반환하고, 끝까지 일치하지 않으면 -1을 반환합니다.
개선된 풀이: O(n) 시간 복잡도 최적화
위 방식은 인덱스마다 매번 slice와 reduce를 호출하므로 시간 복잡도가 O(n²)입니다. 배열이 길어지면 성능이 크게 저하될 수 있습니다.
전체 합계를 미리 구해 둔 뒤, 순회하면서 왼쪽 합만 누적 업데이트하면 오른쪽 합은 전체 합 − 왼쪽 합 − 현재 요소로 한 번에 계산할 수 있습니다. 이렇게 하면 시간 복잡도를 O(n)으로 줄일 수 있습니다.
const balancingIndexOptimized = (arr = []) => {
const total = arr.reduce((acc, x) => acc + x, 0);
let leftSum = 0;
for (let i = 0; i < arr.length; i++) {
const rightSum = total - leftSum - arr[i];
if (leftSum === rightSum) {
return i;
}
leftSum += arr[i];
}
return -1;
};
console.log(balancingIndexOptimized([1, 2, 3, 4, 3, 2, 1])); // 3마무리
균형 인덱스 문제는 누적 합(prefix sum) 개념을 활용하는 대표적인 알고리즘 연습 문제입니다. 단순 구현으로도 충분히 해결할 수 있지만, 전체 합을 미리 계산해 두고 왼쪽 합만 갱신하는 방식을 사용하면 불필요한 반복 계산을 제거해 훨씬 효율적인 코드를 작성할 수 있습니다.