문제 설명
정수 배열 arr을 첫 번째 인수로, 단일 정수 target을 두 번째 인수로 받는 JavaScript 함수를 작성해야 합니다. 이 함수는 크기가 최소 2인 연속된 하위 배열(subarray) 중에서 그 합이 k의 배수, 즉 n * k(n은 임의의 정수)가 되는 경우가 존재하는지 확인해야 합니다.
조건을 만족하는 하위 배열이 존재하면 true를, 존재하지 않으면 false를 반환합니다.
입력 예시
const arr = [23, 2, 6, 4, 7];
const target = 6;
출력 결과
const output = true;
출력 설명
배열 전체인 [23, 2, 6, 4, 7]이 크기 5(2 이상)의 연속 하위 배열이며, 그 합은 42입니다. 42는 6 × 7이므로 6의 배수에 해당하고, 따라서 결과는 true가 됩니다.
해결 접근 방식
이 문제는 누적 합(prefix sum)과 나머지 연산을 활용하면 선형 시간에 효율적으로 해결할 수 있습니다.
핵심 아이디어는 다음과 같습니다.
- 배열을 순회하면서 누적 합을 구하고,
target으로 나눈 나머지를 계산합니다. - 동일한 나머지 값이 두 번 등장했다면, 그 사이 구간의 합은 반드시
target의 배수입니다. - 나머지 값이 처음 등장한 인덱스를 해시 객체에 저장하고, 같은 나머지가 다시 나타났을 때 두 인덱스의 차이가 1보다 크면(즉, 하위 배열의 길이가 2 이상이면)
true를 반환합니다. - 경계 조건 처리를 위해 초기값으로
hash[0] = -1을 설정합니다. 이렇게 하면 배열의 시작부터 특정 지점까지의 합이k의 배수인 경우도 올바르게 처리할 수 있습니다.
구현 코드
const arr = [23, 2, 6, 4, 7];
const target = 6;
const checkSubarraySum = (arr = [], target = 1) => {
let sum = 0;
const hash = {};
hash[0] = -1;
for (let i = 0; i < arr.length; i++) {
sum += arr[i];
if (target != 0) sum %= target;
if (hash[sum] !== undefined) {
if (i - hash[sum] > 1) return true;
} else {
hash[sum] = i;
}
};
return false;
};
console.log(checkSubarraySum(arr, target));
실행 결과
콘솔에 출력되는 결과는 다음과 같습니다.
true
복잡도 분석
- 시간 복잡도: O(n) — 배열을 한 번만 순회하면 됩니다.
- 공간 복잡도: O(min(n, k)) — 해시 객체에는 나머지 값별 인덱스가 저장됩니다.
브루트 포스 방식으로 모든 하위 배열을 검사하면 O(n²)의 시간이 걸리지만, 위와 같이 누적 합의 나머지를 활용하면 대규모 입력에서도 빠르게 동작하는 효율적인 솔루션을 만들 수 있습니다.