[코딩테스트] 45. 열과 구간 쿼리 2

윤설안

May 21, 2025

Contents

문제 제한사항 예시 풀이

문제

💡

정수 배열 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

예시

풀이

❗

해당 문제는 queries의 인덱스의 크기의 역할이 정해져 있기 때문에 우선 적으로 그 역할에 맞게 변수를 선언해주었다. 1번index는 arr를 탐색 할 시작 지점start이고, 2번index는 arr를 탐색 할 마지막 지점end이다. 그리고 3번index는 해당 숫자보다 큰 값 중 가장 작은 값을 고르는 기준num이 된다.

min 조건에 맞는 값 중에 가장 작은 값을 저장할 변수 이다. 처음 값을 문제에 제한 상항에 맞춰서 설정 해주었다. found 는 기본을 false로 지정해주고 if문을 통과하면 ture로 변경이되고, 그 아래 로직에서 if문을 거치지 않았으면 false이기 때문에 false이면 num보다는 무조건 작은 값이기 때문에 조건에 맞게 -1이 배열에 저장 되도록 하였다.

arr 를 queries의 조건으로 모두 조회를 해야하기 때문에 for문을 사용하여 위에서 지정해준 변수를 이용하여 모든 조건을 조회 하였다.


public class ex24 {
    public static void main(String[] args) {
        int[] arr = {0, 1, 2, 4, 3};
        int[][] queries = {{0, 4, 2}, {0, 3, 2}, {0, 2, 2}};
        int[] answer = new int[queries.length];


        for (int i = 0; i < queries.length; i++) {
            int start = queries[i][0];
            int end = queries[i][1];
            int num = queries[i][2];
            int min = 1000001;
            boolean found = false;

            for (int j = start; j <= end; j++) {
                if (num < arr[j] && arr[j] < min) {
                    min = arr[j];
                    found = true;
                }
            }
            if (found) {
                answer[i] = min;
            } else {
                answer[i] = -1;
            }
        }
    }
}