수열과 구간 쿼리 2

https://school.programmers.co.kr/learn/courses/30/lessons/181923

프로그래머스

---

문제 설명
정수 배열 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]

---

입출력 예 설명
입출력 예 #1

• 첫 번째 쿼리의 범위에는 0, 1, 2, 4, 3이 있으며 이 중 2보다 크면서 가장 작은 값은 3입니다.
• 두 번째 쿼리의 범위에는 0, 1, 2, 4가 있으며 이 중 2보다 크면서 가장 작은 값은 4입니다.
• 세 번째 쿼리의 범위에는 0, 1, 2가 있으며 여기에는 2보다 큰 값이 없습니다.
• 따라서 [3, 4, -1]을 return 합니다.

---

저번에 풀었던 문제랑 유사한 문제입니다. 여기서는 조건이 조금 달라졌네요.

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

이번에도 이중 반복문을 사용해서 문제를 풀면 됩니다.

최솟값 min_arr은 간단하게 2가지 방법으로 할 수 있는데,

1) max(arr)을 사용해서 arr의 최댓값을 최솟값으로 설정하기

2) min_arr = 1000001을 사용해서 문제 조건의 최댓값 + 1로 설정하기

로 나뉘어 집니다.

 

저는 2번을 활용해서 문제를 풀어보겠습니다.

def solution(arr, queries):
    # 최솟값들을 저장할 배열
    answer = []
    # 모든 쿼리에 대해 s, e, k 설정
    for s, e, k in queries:
        # 최소값 초기화: 1,000,001
        min_arr = 1000001
        # 모든 s <= i <= e에 대해 탐색
        for i in range(s, e + 1):
            # arr[i]가 k보다 크면서 min_arr보다 작을 때
            if k < arr[i] < min_arr:
                # min_arr 갱신
                min_arr = arr[i]
        # 한 번도 갱신되지 않았다면
        if min_arr == 1000001:
            # -1을 배열에 추가
            answer.append(-1)
        # 갱신되었다면 해당 값을 추가
        else:
            answer.append(min_arr)
    return answer

1,000,001을 갱신 기점으로 사용해서 갱신 여부를 확인합니다.

갱신되지 않았다면 조건에 만족하는 값들이 없으므로 -1을, 갱신되었다면 해당 값을 answer에 추가합니다.

 

어려운 문제는 아니었습니다.