이 문제에서는 크기가 n인 배열 arr[]와 하나 이상의 쿼리가 주어집니다. 각 쿼리는 두 값 (L, R)으로 구성되며, 우리의 과제는 부분 배열(subarray)에 포함된 서로 다른(distinct) 요소의 개수를 구하는 프로그램을 작성하는 것입니다.
문제 설명
주어진 쿼리에 대해 인덱스 (L-1)부터 (R-1)까지의 부분 배열 안에 존재하는 서로 다른 정수의 총 개수를 찾아야 합니다.
예제로 이해하기
입력
arr[] = {4, 6, 1, 3, 1, 6, 5}
query = {1, 4}출력
4
설명
쿼리 1: L = 1, R = 4일 때, 인덱스 0부터 3까지의 요소 {4, 6, 1, 3}은 모두 서로 다르므로 개수는 4입니다.
쿼리 2: L = 2, R = 6일 때, 인덱스 1부터 5까지의 요소 {6, 1, 3, 1, 6} 중 서로 다른 값은 {6, 1, 3}의 3개입니다.
해결 접근 방식
1. 단순 순회 방식
각 쿼리를 처리하는 가장 간단한 방법은 배열을 L부터 R까지 순회하면서 요소들을 집합(set)에 저장하는 것입니다. 이때 집합의 크기가 곧 해당 쿼리의 답이 됩니다. 이전 글(Set 1)에서 다룬 방식과 동일하지만, 쿼리마다 최대 O(N)의 시간이 걸릴 수 있어 쿼리가 많아지면 비효율적입니다.
2. 세그먼트 트리(Segment Tree) 활용
더 효율적인 방법은 세그먼트 트리 자료구조를 사용하는 것입니다. 세그먼트 트리는 정보를 구간(segment) 단위로 저장하는 특수한 트리 구조로, 주어진 범위에 대한 서로 다른 요소의 개수를 저장할 수 있습니다.
세그먼트 트리의 리프 노드는 배열의 개별 요소를 나타내고, 리프가 아닌 노드는 해당 구간에 대한 연산 결과값을 나타냅니다. 여기서는 각 구간에 속한 서로 다른 요소들의 목록을 저장하며, 구현에는 C++ STL의 set 컨테이너를 사용합니다.
구현 코드
#include <bits/stdc++.h>
using namespace std;
set<int>* segmentTree;
void CreateSegmentTree(int i, int s, int e, int arr[]) {
if (s == e) {
segmentTree[i].insert(arr[s]);
return;
}
CreateSegmentTree(2 * i, s, (s + e) / 2, arr);
CreateSegmentTree(1 + 2 * i, 1 + (s + e) / 2, e, arr);
segmentTree[i].insert(segmentTree[2 * i].begin(), segmentTree[2 * i].end());
segmentTree[i].insert(segmentTree[2 * i + 1].begin(), segmentTree[2 * i + 1].end());
}
set<int> findDistSubarray(int node, int l, int r, int a, int b) {
set<int> left, right, distinctSubarray;
if (b < l || a > r)
return distinctSubarray;
if (a <= l && r <= b)
return segmentTree[node];
left = findDistSubarray(2 * node, l, (l + r) / 2, a, b);
distinctSubarray.insert(left.begin(), left.end());
right = findDistSubarray(1 + 2 * node, 1 + (l + r) / 2, r, a, b);
return distinctSubarray;
}
int main() {
int arr[] = {4, 6, 1, 3, 1, 6, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int query[] = {1, 4};
int i = (int)ceil(log2(n));
i = (2 * (pow(2, i))) - 1;
segmentTree = new set<int>[i];
CreateSegmentTree(1, 0, n - 1, arr);
set<int> distCount = findDistSubarray(1, 0, n - 1, (query[0]-1), (query[1]-1));
cout << "부분 배열에 포함된 서로 다른 요소의 개수는 " << distCount.size() << "개입니다";
return 0;
}출력
부분 배열에 포함된 서로 다른 요소의 개수는 4개입니다
참고 사항
위 코드에서는 쿼리 범위가 왼쪽 자식 구간에만 걸치는 경우를 처리하고 있습니다. 범위가 양쪽 자식 구간에 모두 걸치는 경우에도 완전한 정확성을 보장하려면 오른쪽 자식의 결과도 distinctSubarray.insert(right.begin(), right.end());와 같이 병합해 주어야 합니다. 또한 각 노드가 set 전체를 저장하므로 메모리 사용량이 커질 수 있다는 점을 유의해야 하며, 상황에 따라 오프라인 쿼리 처리 기법이나 머지 소트 트리 같은 대안도 고려할 수 있습니다.