Level 0. 수열과 구간 쿼리 2

Level 0. 수열과 구간 쿼리 2

 

 

정렬하지 않고 순회하면서 k보다 큰 원소들에 대해서만 최솟값을 구하면 한 쿼리당 O(n) 시간에 해결할 수 있다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(vector<int> arr, vector<vector<int>> queries)
{
    size_t size = queries.size();
    vector<int> answer(size);

    for (int i = 0; i < size; ++i)
    {
        int t_min = 1'000'001;

        for (int j = queries[i][0]; j <= queries[i][1]; ++j)
            if (queries[i][2] < arr[j])
                t_min = min(t_min, arr[j]);

        answer[i] = (t_min != 1'000'001) ? t_min : -1;
    }

    return answer;
}