[Programmers] #181923 - 수열과 구간 쿼리 2 [Java][C++][Python]

문제 링크

---

1. 아이디어

각 쿼리 [s, e, k]에 대해 s부터 e까지의 구간을 순회하면서 k보다 크면서 가장 작은 값을 찾는다. 답을 매우 큰 값(INF)으로 초기화해두고 구간을 순회하며 k보다 크면서 지금까지 찾은 값보다 작은 원소를 만날 때마다 갱신하고, 순회가 끝난 뒤에도 값이 INF 그대로면 조건을 만족하는 원소가 없다는 뜻이므로 -1로 바꿔서 저장한다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N \times Q)$	$O(Q)$

($N$ = arr의 길이, $Q$ = queries의 길이)

---

3. 코드

풀이 [Java][C++][Python]

import java.util.*;

class Solution {

    static int INF = 1_000_001;

    public int[] solution(int[] arr, int[][] queries) {
        int[] ans = new int[queries.length];
        Arrays.fill(ans, INF);

        for (int i = 0; i < queries.length; i++) {
            int s = queries[i][0];
            int e = queries[i][1];
            int k = queries[i][2];

            for (int j = s; j <= e; j++) {
                if (arr[j] > k && arr[j] < ans[i]) ans[i] = arr[j];
            }

            if (ans[i] == INF) ans[i] = -1;
        }

        return ans;
    }
}

#include <bits/stdc++.h>
using namespace std;

int INF = 1'000'001;

vector<int> solution(vector<int> arr, vector<vector<int>> queries) {
    vector<int> v(queries.size(), INF);

    for (int i = 0; i < queries.size(); i++) {
        int s = queries[i][0];
        int e = queries[i][1];
        int k = queries[i][2];

        for (int j = s; j <= e; j++) {
            if (arr[j] > k && arr[j] < v[i]) v[i] = arr[j];
        }

        if (v[i] == INF) v[i] = -1;
    }

    return v;
}

INF = 1_000_001


def solution(arr, queries):
    ans = [INF] * len(queries)

    for i, (s, e, k) in enumerate(queries):
        for j in range(s, e + 1):
            if arr[j] > k and arr[j] < ans[i]:
                ans[i] = arr[j]

        if ans[i] == INF:
            ans[i] = -1

    return ans

---