이 문제에서는 n개의 정수로 이루어진 배열 arr[]과 각각 정수 k를 담고 있는 Q개의 쿼리가 주어집니다. 우리의 목표는 배열 접미사(Suffix) 구간에 존재하는 고유한 정수의 개수를 구하는 쿼리를 처리하는 프로그램을 작성하는 것입니다.
문제 설명
각 쿼리마다 인덱스 k부터 n까지, 즉 arr[k]부터 arr[n]까지 범위 안에 포함된 서로 다른 원소(고유한 값)의 개수를 찾아야 합니다.
배열은 1부터 시작하는 인덱스(1-indexed)를 사용합니다.
예제로 문제 이해하기
입력
arr[] = {5, 1, 2, 1, 6, 5}, n = 6, Q = 3, query = {1, 3, 4}
출력
4 4 3
설명
쿼리 1: k = 1, N = 6 → arr[1]부터 arr[6]까지 고유 원소 개수 = 4 쿼리 2: k = 3, N = 6 → arr[3]부터 arr[6]까지 고유 원소 개수 = 4 쿼리 3: k = 4, N = 6 → arr[4]부터 arr[6]까지 고유 원소 개수 = 3
해결 방법
1. 단순한 접근 방식
가장 직관적인 방법은 쿼리가 들어올 때마다 인덱스 k부터 n까지 배열을 순회하며 고유한 원소의 개수를 세는 것입니다. 하지만 쿼리마다 매번 구간을 다시 탐색해야 하므로 시간 복잡도가 O(Q × n)에 달해, 입력 크기가 커질 경우 비효율적입니다.
2. 효율적인 접근 방식 — 사전 계산 활용
더 나은 해법은 사전 계산(precomputation)입니다. 배열의 마지막 원소부터 시작하여, "각 인덱스 위치부터 배열 끝까지의 고유 원소 개수"를 미리 계산해 저장해 둡니다.
- 중복 원소의 중복 추가를 방지하기 위해
unordered_set(해시 셋)을 사용합니다. - 배열을 역순으로 순회하며 원소를 집합에 삽입하고, 그 시점의 집합 크기를 보조 배열(distIntCount)에 기록합니다.
- 이렇게 하면 각 쿼리를 O(1) 만에 즉시 답할 수 있습니다.
전체 시간 복잡도는 전처리에 O(n), 각 쿼리 처리에 O(1)이므로 총 O(n + Q)입니다. 쿼리 수가 많을수록 그 효율성이 극대화됩니다.
솔루션 구현 코드
#include <bits/stdc++.h>
using namespace std;
void solveQueries_DistInt(int n, int arr[], int Q, int queries[]) {
unordered_set<int> uniqueInts;
int distIntCount[n + 1];
for (int i = n - 1; i >= 0; i--) {
uniqueInts.insert(arr[i]);
distIntCount[i + 1] = uniqueInts.size();
}
for (int i = 0; i < Q; i++)
cout << "For Query " << (i+1)
<< ": the number of distinct integers in Suffix is "
<< distIntCount[queries[i]] << endl;
}
int main() {
int n = 6, Q = 3;
int arr[n] = {5, 1, 2, 1, 6, 5};
int queries[Q] = {1, 3, 4};
solveQueries_DistInt(n, arr, Q, queries);
return 0;
}
실행 결과
For Query 1: the number of distinct integers in Suffix is 4 For Query 2: the number of distinct integers in Suffix is 4 For Query 3: the number of distinct integers in Suffix is 3
마무리
접미사 구간의 고유 원소 개수를 구하는 문제는 역방향 순회와 해시 셋을 결합한 사전 계산 기법으로 효율적으로 해결할 수 있습니다. 단순 반복 방식은 O(Q × n)의 시간이 소요되지만, 이 방식은 전처리 이후 각 쿼리를 상수 시간에 처리하므로 대량의 쿼리가 발생하는 실무 환경에서 특히 유용한 패턴입니다.