이 문제에서는 크기가 n인 배열 arr[]와 Q개의 쿼리가 주어집니다. 각 쿼리는 두 개의 인덱스 l과 r로 이루어져 있으며, 목표는 각 쿼리에 대해 해당 범위의 부분 배열에 포함된 서로 다른(고유한) 요소의 개수를 구하는 프로그램을 C++로 작성하는 것입니다.
문제 설명
각 쿼리마다 arr[l]부터 arr[r]까지의 부분 배열 안에 있는 서로 다른 정수의 총 개수를 계산해야 합니다. 즉, 같은 값이 여러 번 나오더라도 한 번만 세면 됩니다.
예시로 이해하기
입력
arr[] = {5, 6, 1, 6, 5, 2, 1}
Q = 2
쿼리: {{1, 4}, {0, 6}}
출력
3 4
설명
쿼리 1: l = 1, r = 4이므로 부분 배열은 {6, 1, 6, 5}입니다. 여기서 서로 다른 요소는 6, 1, 5로 총 3개입니다.
쿼리 2: l = 0, r = 6이므로 부분 배열은 {5, 6, 1, 6, 5, 2, 1}입니다. 여기서 서로 다른 요소는 5, 6, 1, 2로 총 4개입니다.
해결 접근 방법
이 문제는 set(집합) 자료구조를 활용하면 깔끔하게 해결할 수 있습니다. set은 중복 값을 허용하지 않는 특성이 있어, 쿼리 범위 [l, r]에 속한 모든 요소를 set에 삽입하면 중복된 값은 자동으로 걸러지고 고유한 값만 저장됩니다. 따라서 삽입이 끝난 후 set의 크기(size)를 반환하면 그것이 곧 해당 범위 내 서로 다른 요소의 개수가 됩니다.
전체 동작 과정을 정리하면 다음과 같습니다.
- 각 쿼리 (l, r)에 대해 빈 set을 생성합니다.
- 인덱스 l부터 r까지의 모든 배열 요소를 set에 삽입합니다.
- set의 size()를 반환합니다. 이 값이 부분 배열의 고유 요소 개수입니다.
구현 예제
#include <bits/stdc++.h>
using namespace std;
int solveQuery(int arr[], int l, int r) {
set<int> distElements;
for (int i = r; i >= l; i--)
distElements.insert(arr[i]);
return distElements.size();
}
int main() {
int arr[] = {5, 6, 1, 6, 5, 2, 1};
int n = sizeof(arr) / sizeof(arr[0]);
int Q = 2;
int query[Q][2] = {{1, 4}, {0, 6}};
for (int i = 0; i < Q; i++)
cout << "쿼리 " << (i + 1) << ": 부분 배열의 서로 다른 요소 개수 = "
<< solveQuery(arr, query[i][0], query[i][1]) << "\n";
return 0;
}
실행 결과
쿼리 1: 부분 배열의 서로 다른 요소 개수 = 3 쿼리 2: 부분 배열의 서로 다른 요소 개수 = 4
복잡도 분석
- 시간 복잡도: 각 쿼리마다 최대 n개의 요소를 set에 삽입하고, 한 번의 삽입에 O(log n)이 소요되므로 전체 시간 복잡도는 O(Q × n × log n)입니다.
- 공간 복잡도: set에 최대 n개의 요소가 저장될 수 있으므로 O(n)입니다.
참고로 배열의 크기와 쿼리의 수가 매우 큰 경우(예: n, Q가 10^5 이상)에는 위의 단순 접근법으로는 시간 초과가 발생할 수 있습니다. 이런 경우에는 Mo's Algorithm(모스 알고리즘)과 같은 오프라인 쿼리 기법이나 머지 소트 트리(Merge Sort Tree), 온라인 처리가 필요하다면 영속 세그먼트 트리(Persistent Segment Tree) 등을 활용하면 훨씬 더 효율적으로 문제를 해결할 수 있습니다.