프로그래머스 수열과 구간 쿼리 2

function solution(arr, queries) {
    const answer = [];

    for (const [s, e, k] of queries) {
        let min = Infinity;

        for (let i = s; i <= e; i++) {
            if (arr[i] > k && arr[i] < min) {
                min = arr[i];
            }
        }

        answer.push(min === Infinity ? -1 : min);
    }

    return answer;
}

🔍 문제 설명

정수 배열 arr와 2차원 정수 배열 queries가 주어집니다.

각 query는 [s, e, k] 형태이며, 다음과 같은 작업을 수행해야 합니다:

• s ≤ i ≤ e인 인덱스 범위에서 arr[i] 중 k보다 크면서 가장 작은 값을 찾습니다.

• 만약 해당 조건을 만족하는 값이 없다면 -1을 결과로 저장합니다.

• 모든 쿼리에 대해 결과를 배열로 반환합니다.

 

🧠 문제 해설

각 쿼리 [s, e, k]는 다음의 의미를 갖습니다:

1. 배열 arr의 s부터 e까지 부분 구간을 살펴봅니다.

2. 그 안에서 k보다 크고, 가장 작은 값 하나만을 찾습니다.

3. 그 값이 없다면 -1을 반환합니다.

 

✅ 최적화된 접근 방식

✔ 핵심 아이디어

• arr[s]부터 arr[e]까지 순회하면서 k보다 크고, 현재까지 찾은 값보다 작은 값이 있으면 갱신합니다.

• 가장 작은 값만 기억해두면 되므로 O(n)으로 해결할 수 있습니다.

 

🔍 코드 해설

• min을 Infinity로 초기화합니다 (어떤 수보다도 크도록).

• s부터 e까지 순회하면서 조건에 맞는 수를 찾습니다.

• 조건: arr[i] > k이면서, 현재 min보다 작을 때만 갱신.

• 찾은 수가 없으면 Infinity 그대로이므로 -1을 넣습니다.