이 글에서는 숫자 배열 arr와 숫자 num을 인자로 받아, 부분 배열 내 모든 요소 쌍의 절대 차이가 num 이하가 되는 가장 긴 부분 배열의 길이를 구하는 자바스크립트 함수를 작성해 보겠습니다. 여기서 말하는 부분 배열은 요소들이 연속적이어도 되고, 연속적이지 않아도 괜찮습니다.
예를 들어 입력이 다음과 같다고 가정해 보겠습니다.
const arr = [7, 9, 8, 6, 6, 3]; const num = 1;
이 경우 함수가 반환해야 하는 결과는 다음과 같습니다.
const output = 3;
그 이유는 조건을 만족하는 가장 긴 부분 배열이 바로 [7, 6, 6]이기 때문입니다. 실제로 |7 − 6| = 1, |6 − 6| = 0으로 이 배열의 모든 쌍은 절대 차이가 1 이하이며, 세 개보다 많은 요소를 포함하면서 이 조건을 만족하는 조합은 존재하지 않습니다.
접근 방식: 버킷 빈도 계산
요소들의 순서는 중요하지 않고 값의 분포만 중요하다는 점에 착안하면, 버킷(bucket) 기반 카운팅 기법으로 문제를 해결할 수 있습니다. 전체 흐름은 다음과 같습니다.
- 배열에서 가장 큰 값을 구한 뒤, 그 크기만큼의 버킷 배열을 생성하고 0으로 초기화합니다.
- 배열을 한 번 순회하면서 각 요소 값에 해당하는 버킷의 값을
num씩 증가시켜, 각 숫자가 등장한 횟수를 기록합니다. - 값의 차이가 1인 인접한 두 버킷의 빈도 합을 모두 검사한 후, 그중 가장 큰 값을 결과로 반환합니다.
예제 배열에서는 값 6이 두 번 등장하고(buckets[6] = 2), 값 7이 한 번 등장하므로(buckets[7] = 1), 인접 버킷의 빈도 합 2 + 1 = 3이 곧 정답이 됩니다. 참고로 위 구현은 num의 기본값인 1을 기준으로 인접한 두 값의 빈도를 비교하는 방식으로 동작합니다.
예제 코드
const arr = [7, 9, 8, 6, 6, 3];
const maximumSubarray = (arr = [], num = 1) => {
if(!arr.length){
return 0;
};
const maximum = arr.reduce((acc, val) => Math.max(acc, val));
const buckets = new Array(maximum + 1);
buckets.fill(0);
const { length } = arr;
for(let i=0; i< length; i++){
buckets[arr[i]] += num;
};
let max = 0;
for(let j=1; j< maximum + 1; j++) {
let curr = buckets[j];
let prev = buckets[j - 1];
if(prev != 0 && prev + curr > max) {
max = prev + curr;
};
};
return max;
};
console.log(maximumSubarray(arr));
실행 결과
코드를 실행하면 콘솔에 다음과 같은 출력이 나타납니다.
3
시간 및 공간 복잡도
배열 순회와 버킷 스캔이 각각 선형 시간에 수행되므로 전체 시간 복잡도는 O(n + m)입니다(n은 배열의 길이, m은 배열의 최댓값). 공간 복잡도는 버킷 배열 크기에 비례하여 O(m)입니다.