JavaScript에서 양의 정수로 이루어진 배열과 하나의 양의 정수를 인수로 받는 함수를 작성해야 합니다.
이 함수의 목표는 배열 전체의 합이 두 번째 인수로 전달된 숫자로 나누어 떨어지도록 만들기 위해, 원본 배열에서 제거해야 하는 가장 짧은 연속 하위 배열(subarray)의 길이를 구해 반환하는 것입니다.
문제 예시
예를 들어, 입력이 다음과 같다고 가정해 보겠습니다.
const arr = [3, 8, 2, 6]; const num = 9;
배열 전체의 합은 3 + 8 + 2 + 6 = 19이며, 19를 9로 나누면 나머지가 1이 됩니다. 여기서 [8, 2]라는 하위 배열(합이 10)을 제거하면 남는 요소의 합은 9가 되어 9로 나누어 떨어집니다.
따라서 기대되는 출력은 다음과 같습니다.
const output = 2
접근 방식: 누적 합과 모듈러 연산 활용
이 문제는 접두사 합(prefix sum)과 모듈러(modulo) 연산을 조합하면 O(n) 시간 복잡도로 효율적으로 해결할 수 있습니다.
핵심 아이디어는 다음과 같습니다.
1. 전체 배열의 합을 num으로 나눈 나머지(diff)를 계산합니다. diff가 0이라면 이미 나누어 떨어지므로 제거할 필요가 없습니다.
2. 배열을 순회하면서 각 위치까지의 누적 합을 num으로 나눈 나머지를 해시 맵에 저장합니다.
3. 현재 누적 합의 나머지에서 diff를 뺀 값(target)이 이전에 등장했다면, 그 두 위치 사이의 구간을 제거했을 때 목표 조건이 충족됩니다.
4. 가능한 모든 경우 중 가장 짧은 구간의 길이를 결과로 반환합니다.
구현 코드
const arr = [3, 8, 2, 6];
const num = 9;
const minimumDeletion = (arr = [], num) => {
// 전체 합을 num으로 나눈 나머지
const diff = arr.reduce((a, b) => a + b) % num;
// 이미 나누어 떨어지면 0, 아니면 일단 배열 전체 길이로 초기화
let res = diff == 0 ? 0 : arr.length;
for (let i = 0, sum = 0, map = {0: -1}; i < arr.length; i++) {
sum += arr[i];
// 제거해야 할 구간을 찾기 위한 목표 나머지 값
const target = (sum % num - diff + num) % num;
if (map[target] != undefined) {
res = Math.min(res, i - map[target]);
};
map[sum % num] = i;
};
// 조건을 만족하는 구간이 없다면 -1 반환
return res == arr.length ? -1 : res;
};
console.log(minimumDeletion(arr, num));실행 결과
위 코드를 실행하면 콘솔에 다음과 같이 출력됩니다.
2
결과값 2는 제거해야 하는 하위 배열 [8, 2]의 길이를 의미합니다. 만약 어떤 하위 배열을 제거해도 조건을 만족할 수 없는 경우에는 함수가 -1을 반환하도록 처리했습니다.