정렬된 n개의 정수 값을 담고 있는 배열 arr이 주어졌다고 가정해 보겠습니다. 또한 크기가 q인 배열 query가 함께 주어지며, query에 포함된 각 값이 배열 arr에 존재하는지 판별해야 합니다. query의 값이 arr에 존재하면 Present와 함께 해당 값이 위치한 인덱스를 출력하고, 존재하지 않으면 Not present와 함께 query 값보다 큰 값 중 최솟값이 위치한 인덱스를 출력합니다. 단, 배열은 1부터 시작하는 인덱스(1-indexed)를 사용한다는 점에 유의해야 합니다.
예를 들어 n = 8, arr = {1, 2, 3, 4, 7, 9, 12, 15}, q = 3, query = {1, 5, 8}이 입력으로 주어진다면 출력은 다음과 같습니다.
Present 1 Not present 5 Not present 6
첫 번째 query 값인 1은 arr의 1번 위치에 존재합니다.
두 번째 query 값인 5는 arr에 존재하지 않습니다. 이 값보다 큰 최솟값은 5번 위치에 있습니다.
마찬가지로 세 번째 query 값인 8도 arr에 존재하지 않으며, 이보다 큰 값은 6번 위치에 있습니다.
문제 해결 접근 방법
이 문제는 C++ STL의 lower_bound 함수를 활용하면 효율적으로 해결할 수 있습니다. lower_bound는 정렬된 범위에서 특정 값 이상이 처음 나타나는 위치를 이진 탐색으로 찾아주는 함수로, 시간 복잡도는 O(log n)입니다. 따라서 쿼리 개수가 많은 경우에도 빠른 검색이 가능합니다.
해결 절차는 다음과 같습니다.
- values라는 벡터를 정의합니다.
- i := 0부터 i < n까지 반복하며 다음을 수행합니다.
- values의 끝에 arr[i]를 삽입합니다.
- i := 0부터 i < q까지 반복하며 다음을 수행합니다.
- idx := values에서 query[i]보다 작지 않은 첫 번째 원소의 위치 - values의 시작 위치
- values[idx]가 query[i]와 같으면 "Present"를 출력합니다.
- 그렇지 않으면 "Not present"를 출력합니다.
- idx + 1을 출력합니다.
예제 코드
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
#include <vector>
#include <iostream>
using namespace std;
void solve(int n, int arr[], int q, int query[]) {
vector<int> values;
for(int i = 0; i < n; i++){
values.push_back(arr[i]);
}
for(int i = 0; i < q; i++) {
int idx = lower_bound(values.begin(), values.end(),
query[i]) - values.begin();
if (values[idx] == query[i])
cout << "Present ";
else
cout << "Not present ";
cout << idx + 1 << endl;
}
}
int main() {
int input_arr[] = {1, 2, 3, 4, 7, 9, 12, 15};
int query_arr[] = {1, 5, 8};
solve(8, input_arr, 3, query_arr);
return 0;
}
입력(stdin)
int input_arr[] = {1, 2, 3, 4, 7, 9, 12, 15};
int query_arr[] = {1, 5, 8};
solve(8, input_arr, 3, query_arr);
출력
Present 1 Not present 5 Not present 6
이처럼 lower_bound를 활용하면 정렬된 배열에서 원하는 값을 O(log n)의 시간 복잡도로 빠르게 검색할 수 있습니다. 값의 존재 여부와 함께 그보다 큰 최솟값의 위치까지 한 번에 확인할 수 있어, 다양한 탐색 문제에서 유용하게 활용됩니다.