⭐코딩 기초 트레이닝 > 수열과 구간 쿼리 2 - Java

 

 

프로그래머스

 

 

 

문제를 이해하는 것 부터 시간이 걸린 문제 

 

 

queries 의 배열이 다음과 같을 때,

query 에서 s,e,k 의미

s = 각 행의 1열에 해당하는 수 -> 0,0,0
e = 각 행의 2열에 해당하는 수 -> 4,3,2
k = 각 행의 3열에 해당하는 수 -> 2,2,2

 

 

arr[] 배열과 함께 예제를 살펴보자 

 

첫번째로 query = [ 0,4,2] 에서 i의 범위는 0<=i<=4 

i = 0,1,2,3,4

arr[i] 값을 비교해야하므로  각 arr[i] 값을 가져오면 0,1,2,4,3 이 온다

k=2 이므로 arr[i] 값 중에 2보다 크면서 가장 작은 값은 3 이 온다

 

두번째로 query = [ 0,3,2 ]  에서 i의 범위는 0<=i <=3

i = 0,1,2,3 

arr[0] = 0, arr[1] = 1, arr[2] = 2, arr[3] = 4 

k=2 이므로 범위에 해당하는 arr[i] 값 중 2보다 크면서 가장 작은 arr[i] 은 arr[3] 값인 4가 온다

 

 

이런식으로 진행 ! 

 

 

 

queries 로 비교해보면 다음과 같은 모양이 된다.

 

*** 정정 i < queries[i][1] -> i <= queries[i][1]

 

 

---

 

 

 

import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
    public static int[] solution(int[] arr, int[][] queries) {
        int[] answer = new int[queries.length];
        Arrays.fill(answer, -1); // 초기값으로 -1을 채워놓습니다.

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

            int minGreaterValue = Integer.MAX_VALUE; // 최소값을 저장할 변수, 일단 최대값으로 초기화합니다.

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

            if (minGreaterValue != Integer.MAX_VALUE) {
                answer[i] = minGreaterValue;
            }
        }

        return answer;
    }

}

 

 

---

 

 

이중 for 문안의 if 절에서 arr[j] < minGreaterValue 조건을 준 이유

 

 

arr[j] < minGreaterValue 조건이 없는 경우 

for (int j = start; j <= end; j++) {
	if (arr[j] > k) {
		minGreaterValue = arr[j];
     }
 }

 if (minGreaterValue != Integer.MAX_VALUE) {
 	answer[i] = minGreaterValue;
 }

 

이때 query 값으로 [ 0,4,2 ] 가 오는 상황을 생각해보자

 

이때 for(int j=s; j<e; j++)  안에서 if(arr[j] < k) 를 만족하는 arr[j] 에는 arr[3]=4 와 arr[4]=3 이 올 수 있다.

마지막으로 j 가 증감함에 따라 minGreaterValue  값에는 3이 온다 

 

 

하지만 다음과 같은 경우는 ?? 

 

 

arr[0,1,2,4,3] -> arr[0,1,2,3,4] 로 변경해서 테스트를 하게되면 reutrn  값으로는 [3,3,-1] 이 와야한다 

 

하지만 그대로 코드를 돌게 되면 j는 증감함에 따라  minGraterValue 값에 값을 저장하기 때문에

query 가 [0,4,2] 인 경우에 2보다 큰수중에 제일 작인 수에 arr[3]=3 이 아닌, arr[4]=4 가 들어오는 것이다

 

따라서 minGraterValue  값에 값을 저장한 후, 조건절에 j가 증감하는 동안 arr[j] < minGraterValue 조건을 거치도록 한다.