문제 개요
배열을 한 개의 요소와 나머지 요소들로 분할했을 때, 그 하나의 요소가 자신을 제외한 나머지 모든 요소들의 곱과 정확히 일치하면 true, 그렇지 않으면 false를 반환하는 함수를 작성해야 합니다.
예를 들어, 입력 배열이 다음과 같다고 가정해 보겠습니다.
const arr = [1, 56, 2, 4, 7];
이 경우 기대하는 출력값은 true입니다. 그 이유는 56이 나머지 요소들의 곱과 같기 때문입니다.
1 * 2 * 4 * 7 = 56
접근 방법
이 문제는 배열을 한 번만 순회하면 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 순회하면서 지금까지 등장한 최댓값(max)을 별도로 추적합니다.
- 최댓값을 제외한 나머지 값들은 계속 곱해 나가며 누적곱(prod)을 만듭니다.
- 현재 값이 기존 최댓값보다 크면, 그동안 빼두었던 최댓값을 누적곱에 반영하고 새 값을 최댓값으로 갱신합니다.
- 순회가 끝난 뒤 최댓값과 누적곱이 서로 같은지 비교하여 결과를 반환합니다.
구현 코드
위 로직을 reduce() 메서드를 사용해 구현한 코드는 다음과 같습니다.
const arr = [1, 56, 2, 4, 7];
const isEqualPartition = arr => {
const creds = arr.reduce((acc, val) => {
let { prod, max } = acc;
if(val > max || !max){
prod *= (max || 1);
max = val;
}else{
prod *= val;
}
return { prod, max };
}, {
prod: 1,
max: null
});
return creds.max === creds.prod;
};
console.log(isEqualPartition(arr));
실행 결과
콘솔에 출력되는 결과는 다음과 같습니다.
true
reduce()를 사용해 배열을 딱 한 번만 순회하므로 이 알고리즘의 시간 복잡도는 O(n)입니다. 또한 누적곱과 최댓값 두 변수만 유지하면 되기 때문에 공간 복잡도 역시 O(1)로 매우 효율적입니다.