[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의 길이. Python은 window에 구간의 값을 모아 공간 $O(N + Q)$)

---

3. 코드

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

import java.util.*;

class Solution {

    static final 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 (k < arr[j] && arr[j] < ans[i]) ans[i] = arr[j];
            }

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

        return ans;
    }
}

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

const int INF = 1'000'001;

vector<int> solution(vector<int> arr, vector<vector<int>> queries) {
    vector<int> ans(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 (k < arr[j] && arr[j] < ans[i]) ans[i] = arr[j];
        }

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

    return ans;
}

def solution(arr, queries):
    ans = []
    for s, e, k in queries:
        window = [x for x in arr[s : e + 1] if x > k]
        ans.append(min(window) if window else -1)

    return ans

Python은 INF 대신 구간에서 k보다 큰 값만 모아 min을 취하고, 그런 값이 없으면 -1로 처리했다.

---