이 문제에서는 배열 arr[]와 여러 개의 쿼리가 주어집니다. 각 쿼리는 세 가지 값 L(시작 인덱스), R(끝 인덱스), val(찾고자 하는 숫자)로 구성됩니다. 우리의 목표는 각 쿼리에 대해 주어진 범위 [L, R] 안에 해당 숫자 val이 존재하는지 확인하는 프로그램을 C++로 작성하는 것입니다.
문제 설명
각 쿼리를 처리할 때마다 주어진 요소 val이 범위 L부터 R 사이의 구간에 포함되어 있는지 판별해야 합니다.
예시를 통해 문제를 이해해 보겠습니다.
입력: arr[] = {4, 8, 1, 7, 2, 9, 3, 5, 1}
Q = 3
query = {{1, 4, 3}, {0, 2, 1}, {4, 7, 2}}
출력:
Not Present
Present
Present
설명
쿼리 1: 범위는 [1, 4]이며, 부분 배열은 {8, 1, 7, 2}입니다. 이 구간에는 3이 없습니다.
쿼리 2: 범위는 [0, 2]이며, 부분 배열은 {4, 8, 1}입니다. 이 구간에는 1이 존재합니다.
쿼리 3: 범위는 [4, 7]이며, 부분 배열은 {2, 9, 3, 5, 1}입니다. 이 구간에는 2가 존재합니다.
해결 접근 방법
방법 1: 단순 순회 (Brute Force)
가장 간단한 방법은 쿼리마다 해당 범위의 부분 배열을 처음부터 끝까지 순회하면서 찾고자 하는 요소가 있는지 일일이 확인하는 것입니다.
예제 코드
#include <iostream>
using namespace std;
bool isElementPresent(int arr[], int L, int R, int val){
for(int i = L; i <= R; i++ ){
if(arr[i] == val){
return true;
}
}
return false;
}
int main(){
int arr[] = {4, 8, 1, 7, 2, 9, 3, 5, 1};
int Q = 3;
int query[Q][3] = {{1, 4, 3}, {0, 2, 1}, {4, 7, 2 }};
for(int i = 0; i < Q; i++){
cout<<"For Query "<<(i+1);
if(isElementPresent(arr, query[i][0], query[i][1], query[i][2]))
cout<<": The given digit "<<query[i][2]<<" is present in the given range\n";
else
cout<<": The given digit "<<query[i][2]<<" is not present in the given range\n";
}
return 0;
}
출력 결과
For Query 1: The given digit 3 is not present in the given range
For Query 2: The given digit 1 is present in the given range
For Query 3: The given digit 2 is present in the given range
이 방법은 루프를 사용하기 때문에 시간 복잡도는 O(Q × N)입니다. 여기서 Q는 쿼리의 개수, N은 배열의 크기를 의미합니다. 쿼리와 배열의 크기가 커질수록 비효율적일 수 있습니다.
방법 2: 세그먼트 트리 활용 (효율적인 접근)
더 나은 해결 방법은 세그먼트 트리(Segment Tree)를 사용하여 가능한 모든 숫자(0~9)의 정보를 저장하는 것입니다. 노드 내에 중복된 요소가 저장되지 않도록 set 자료구조를 활용하면 됩니다. set은 중복을 자동으로 제거하는 특성이 있어, 각 노드가 저장하는 요소의 개수를 최대 10개로 제한할 수 있습니다.
이렇게 트리를 구성한 후에는 각 쿼리에 대해 해당 범위 내에 요소가 존재하는지 빠르게 확인할 수 있습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
set<int> SegTree[36];
void buildSegmentTree(int* arr, int index, int start, int end) {
if (start == end) {
SegTree[index].insert(arr[start]);
return;
}
int middleEle = (start + end) >> 1;
buildSegmentTree(arr, 2 * index, start, middleEle);
buildSegmentTree(arr, 2 * index + 1, middleEle + 1, end);
for (auto it : SegTree[2 * index])
SegTree[index].insert(it);
for (auto it : SegTree[2 * index + 1])
SegTree[index].insert(it);
}
bool isElementPresent(int index, int start, int end, int L, int R, int val){
if (L <= start && end <= R) {
if (SegTree[index].count(val) != 0) {
return true;
}
else
return false;
}
if (R < start || end < L) {
return false;
}
int middleEle = (start + end) >> 1;
bool isPresentInLeftSubArray = isElementPresent((2 * index), start,middleEle, L, R, val);
bool isPresentInRightSubArray = isElementPresent((2 * index + 1),(middleEle + 1), end, L, R, val);
return isPresentInLeftSubArray or isPresentInRightSubArray;
}
int main(){
int arr[] = {4, 8, 1, 7, 2, 9, 3, 5, 1};
int n = sizeof(arr)/sizeof(arr[0]);
int Q = 3;
int query[Q][3] = {{1, 4, 3}, {0, 2, 1}, {4, 7, 2 }};
buildSegmentTree(arr, 1, 0, (n - 1));
for(int i = 0; i < Q; i++){
cout<<"For Query "<<(i+1);
if(isElementPresent(1, 0, (n - 1), query[i][0], query[i][1], query[i][2]))
cout<<": The given digit "<<query[i][2]<<" is present in the given range\n";
else
cout<<": The given digit "<<query[i][2]<<" is not present in the given range\n";
}
return 0;
}
출력 결과
For Query 1: The given digit 3 is not present in the given range
For Query 2: The given digit 1 is present in the given range
For Query 3: The given digit 2 is present in the given range
세그먼트 트리를 사용하면 트리 구축에 O(N log N)의 시간이 걸리지만, 이후 각 쿼리는 O(log N) 시간 안에 처리할 수 있습니다. 따라서 쿼리가 많은 경우 단순 순회 방식(O(Q × N))보다 훨씬 효율적입니다.