문제
리터럴 값으로 이루어진 배열 arr을 첫 번째 인수로, 숫자 num을 두 번째 인수로 받는 JavaScript 함수를 작성해야 합니다. 이 함수는 배열에서 정확히 num개의 서로 다른(고유한) 요소를 포함하는 부분 배열(subarray)의 개수를 세어 반환해야 합니다.
예를 들어, 함수에 다음과 같은 입력이 주어졌다고 가정해 보겠습니다.
const arr = [12, 15, 12, 15, 18];
const num = 2;
그렇다면 출력은 다음과 같아야 합니다.
const output = 7;
출력 설명
정확히 2개의 서로 다른 요소로 구성된 부분 배열은 다음과 같습니다.
[12,15], [15,12], [12,15], [15,18], [12,15,12], [15,12,15], [12,15,12,15]
접근 방식: 슬라이딩 윈도우
이 문제는 슬라이딩 윈도우(Sliding Window) 기법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
"정확히 num개의 고유 요소를 가진 부분 배열의 수 = 최대 num개의 고유 요소를 가진 부분 배열의 수 − 최대 (num − 1)개의 고유 요소를 가진 부분 배열의 수"
내부 헬퍼 함수 findDistinct는 최대 count개의 고유 요소를 가지는 부분 배열의 총 개수를 계산합니다. 각 요소의 등장 횟수를 해시 객체(map)에 기록하고, 고유 요소의 수가 count를 초과하면 왼쪽 포인터(ptr)를 앞으로 이동시키며 윈도우를 축소합니다. 매 단계마다 현재 오른쪽 끝점을 공유하는 유효한 부분 배열의 개수(right - ptr + 1)를 결과에 더해 누적합니다.
예제 코드
const arr = [12, 15, 12, 15, 18];
const num = 2;
const distinctSubarrays = (arr = [], num = 1) => {
const findDistinct = (count) => {
const map = {};
let ptr = 0;
let distinct = 0;
let res = 0;
for(let right = 0; right < arr.length; right++){
const num = arr[right];
map[num] = (map[num] || 0) + 1;
if(map[num] === 1){
distinct += 1;
};
while(distinct > count){
map[arr[ptr]] -= 1;
if(map[arr[ptr]] === 0){
distinct -= 1;
};
ptr += 1;
};
res += right - ptr + 1;
};
return res;
};
return findDistinct(num) - findDistinct(num - 1)
};
console.log(distinctSubarrays(arr, num));
실행 결과
콘솔에 출력되는 결과는 다음과 같습니다.
7
복잡도 분석
배열의 길이를 n이라고 할 때, 두 포인터가 각각 배열을 한 번씩만 순회하므로 시간 복잡도는 O(n)입니다. 또한 고유 요소의 개수에 비례하여 해시 맵 저장 공간이 필요하므로 공간 복잡도 역시 O(n)입니다. 브루트포스 방식(O(n²))보다 훨씬 효율적으로 대용량 배열에서도 빠르게 동작합니다.