왓슨은 셜록에게 길이가 N인 배열 A를 하나 건네줍니다. 그리고 이 배열 안에서 어떤 요소를 기준으로 왼쪽 요소들의 합과 오른쪽 요소들의 합이 서로 같아지는 지점이 존재하는지 판별해 보라고 요청합니다. 흔히 '셜록 배열(Sherlock and Array)' 또는 '균형점 찾기'라 불리는 대표적인 배열 알고리즘 문제입니다.
우리는 이 동작을 수행하는 함수를 작성해야 하며, 함수는 다음 조건을 만족해야 합니다.
- 숫자 배열을 인수로 받습니다.
- 조건을 만족하는 요소가 존재하면 해당 요소의 인덱스를 반환합니다.
- 조건을 만족하는 요소가 없으면 -1을 반환합니다.
효율적인 접근 방법
각 인덱스마다 왼쪽 합과 오른쪽 합을 매번 새로 계산하는 단순한 방법도 있지만, 이 경우 시간 복잡도가 O(N²)까지 증가할 수 있습니다. 대신 아래 방법을 사용하면 배열을 한 번만 순회하여 O(N) 시간 복잡도로 문제를 해결할 수 있습니다.
- 먼저 reduce() 메서드로 배열 전체의 합을 구합니다.
- 배열을 순회하면서 현재 요소 값을 전체 합에서 빼면, 그 결과값이 곧 현재 위치 기준의 '오른쪽 합'이 됩니다.
- 오른쪽 합이 지금까지 누적된 '왼쪽 합'과 같다면 해당 인덱스가 바로 정답입니다.
- 같지 않다면 현재 요소를 왼쪽 합에 더한 뒤 다음 인덱스로 넘어갑니다.
예제 코드
const arr = [1, 2, 3, 4, 5, 7, 3];
const arr2 = [4, 6, 3, 4, 5, 2, 1];
const isSherlockArray = arr => {
let sum = arr.reduce((acc, val) => acc + val);
let leftSum = 0;
for(let i = 0; i < arr.length; i++){
sum -= arr[i];
if(sum === leftSum){
return i;
}
leftSum += arr[i];
}
return -1;
};
console.log(isSherlockArray(arr));
console.log(isSherlockArray(arr2));실행 결과
콘솔에는 아래와 같이 출력됩니다.
4 -1
결과 분석
첫 번째 배열 [1, 2, 3, 4, 5, 7, 3]의 경우, 인덱스 4에 있는 요소 5를 기준으로 왼쪽 합(1 + 2 + 3 + 4 = 10)과 오른쪽 합(7 + 3 = 10)이 일치하므로 4가 반환됩니다. 반면 두 번째 배열 [4, 6, 3, 4, 5, 2, 1]에서는 왼쪽 합과 오른쪽 합이 같아지는 요소가 존재하지 않으므로 -1이 출력됩니다.