코테32)수열과 구간쿼리2

📝 문제설명

정수 배열 arr와 2차원 정수 배열 queries이 주어집니다. queries의 원소는 각각 하나의 query를 나타내며, [s, e, k] 꼴입니다.

각 query마다 순서대로 s ≤ i ≤ e인 모든 i에 대해 k보다 크면서 가장 작은 arr[i]를 찾습니다.

각 쿼리의 순서에 맞게 답을 저장한 배열을 반환하는 solution 함수를 완성해 주세요.
단, 특정 쿼리의 답이 존재하지 않으면 -1을 저장합니다.

제한사항
1 ≤ arr의 길이 ≤ 1,000
0 ≤ arr의 원소 ≤ 1,000,000
1 ≤ queries의 길이 ≤ 1,000
0 ≤ s ≤ e < arr의 길이
0 ≤ k ≤ 1,000,000
입출력 예
arr queries result
[0, 1, 2, 4, 3][0, 4, 2],[0, 3, 2],[0, 2, 2]] [3, 4, -1]

내 풀이:

def solution(arr, queries):
    answer = []
    s, e, k = 0, 0, 0
    for i in queries:
        s,e,k = i[0], i[1], i[2]
        new = []
        for v in range(s, e + 1):
            if arr[v] > k:
                new.append(arr[v])
        if new == []:
            new.append(-1)
        answer.append(min(new))
    return answer

i) 각 query의 [s, e, k]를 찾기 -> for loop를 사용해서 s,e,k에 각 query의 원소들을 넣었다
ii) s ≤ i ≤ e 모든 i에 대해 k보다 크면서 가장 작은 arr[i]를 찾습니다.-> for loop안에 다른 s부터 e+1까지의 range를 가진 for loop를 만들어 arr[v] > k 인지 확인 후 new list에 넣어준다.
iii) 특정 쿼리의 답이 존재하지 않으면 -1을 저장 -> new list에 아무것도 없다는 것은 k보다 크면서 가장작은 수가 없다는 뜻이니까 new list에 -1을 저장했다
iv) 각 쿼리의 순서에 맞게 답을 저장한 배열을 반환하는 solution 함수를 완성-> answer list에 가장 작은 수를 넣기 위해 min함수를 사용했다

Time complexity: O(n*m)
The outer loop runs for each query, so it's O(n)
The inner loop runs for each element in the subarray, so it's O(m)

모든 i에 대해 k보다 크면서 가장 작은 arr[i]를 찾기위해 new list를 만들었는데list를 하나만 가져와서 만들 수 있을 거 같다는 생각이 들었다.