구간 안 같은 상품 쌍 개수

자바스크립트 코딩테스트 문제로 offline-range-query 주제를 연습해보세요. 난이도는 hard이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

today hard offline-range-query 함수명: countEqualPairsInRanges 제한 시간: 500ms

여러 구간마다 같은 값을 가진 서로 다른 두 상품 위치 쌍이 몇 개인지 빠르게 구하세요.

문제 설명

정수 배열 values와 구간 질의 배열 queries가 주어집니다.

각 질의는 [left, right] 형태이며, values[left]부터 values[right]까지의 닫힌 구간을 의미합니다. 각 구간 안에서 i < j이고 values[i] === values[j]인 위치 쌍의 개수를 구해, 질의가 들어온 순서대로 배열에 담아 반환하는 countEqualPairsInRanges 함수를 작성하세요.

제한사항

1 <= values.length <= 100,000
1 <= queries.length <= 100,000
-1,000,000,000 <= values[i] <= 1,000,000,000
각 질의는 [left, right] 형태입니다.
0 <= left <= right < values.length
반환 배열의 k번째 값은 queries[k]의 답이어야 합니다.
정답은 JavaScript의 안전한 정수 범위 안에 들어옵니다.

예시

입력: values = [1, 2, 1, 1, 2], queries = [[0, 4], [1, 3], [2, 2]] → 출력: [4, 1, 0]
입력: values = [5, 5, 5, 5], queries = [[0, 3], [1, 2]] → 출력: [6, 1]
입력: values = [1, 2, 3], queries = [[0, 2], [1, 1]] → 출력: [0, 0]
입력: values = [3, 1, 3, 2, 3, 1], queries = [[0, 5], [1, 4], [2, 4]] → 출력: [4, 1, 1]

힌트

한 구간을 매번 처음부터 세면 최악의 경우 너무 느립니다.
질의를 원래 순서대로 처리하지 않아도, 마지막에 답만 원래 인덱스에 넣으면 됩니다.
현재 구간에 값 x가 c번 들어 있을 때 x를 하나 더 추가하면 새로 생기는 같은 값 쌍은 c개입니다.

해설

구간 [left, right]의 답은 값별 등장 횟수로 계산할 수 있습니다. 어떤 값이 구간 안에 c번 등장한다면, 그 값만으로 만드는 위치 쌍은 c * (c - 1) / 2개입니다.

하지만 질의마다 전체 구간을 새로 훑으면 O(n * q)가 될 수 있습니다. values.length와 queries.length가 모두 클 때는 통과하기 어렵습니다.

이 문제는 Mo’s algorithm으로 풀 수 있습니다. 질의를 left의 블록 번호 기준으로 묶고, 같은 블록 안에서는 right가 증가하는 순서로 정렬합니다. 그러면 이전 질의의 구간에서 다음 질의의 구간으로 이동할 때 왼쪽과 오른쪽 포인터를 조금씩만 움직이며 현재 구간 상태를 재사용할 수 있습니다.

현재 구간의 답 pairCount와 값별 빈도 freq를 유지합니다.

// 값 x 추가 전 빈도가 c라면, 새 원소는 기존 c개와 각각 쌍을 만든다.
pairCount += c;
freq[x] = c + 1;

// 값 x 제거 전 빈도가 c라면, 제거 뒤 남는 c - 1개와 만들던 쌍이 사라진다.
freq[x] = c - 1;
pairCount -= c - 1;

예를 들어 values = [1, 2, 1, 1, 2]의 전체 구간 [0, 4]에서는 값 1이 3번, 값 2가 2번 등장합니다. 따라서 같은 값 쌍은 3C2 + 2C2 = 3 + 1 = 4개입니다.

정렬된 질의를 처리하며 각 질의의 답은 원래 질의 인덱스 위치에 저장해야 합니다. 질의 처리 순서와 반환 순서가 다르기 때문입니다.

블록 크기를 대략 Math.sqrt(n)으로 잡으면 시간 복잡도는 보통 O((n + q) * sqrt(n)) 수준으로 동작합니다. 값의 범위가 크므로 빈도는 배열 인덱스가 아니라 Map으로 관리하는 편이 안전합니다.

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

아직 실행하지 않았습니다.

실행 결과