[프로그래머스 코딩테스트] 수열과 구간 쿼리 2(Java)

  문제 설명

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

class Solution {
    public int[] solution(int[] arr, int[][] queries) {
        int[] answer = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int s = queries[i][0];
            int e = queries[i][1];
            int k = queries[i][2];
            int min = Integer.MAX_VALUE;
            for (int j = s; j <= e; j++) {
                if (arr[j] < min && k < arr[j]) {
                    min = arr[j];
                }
            }
            if (min != Integer.MAX_VALUE) {
                answer[i] = min;
            } else {
                answer[i] = -1;
            }
        }
        return answer;
    }
}

  배열 answer를 생성하고 answer의 크기는 queries의 길이로 지정합니다.

  바깥 for문이 queries의 길이만큼 순회합니다.

  문제에서 요구하는 조건에 맞추어 변수 s, e, k를 각각 생성했습니다.

  min은 값을 지정하기 애매하여 Integer 클래스의 MAX_VALUE를 이용했습니다. 가장 큰 값을 할당한 뒤, 이후 작은 수가 있으면 그 값으로 갱신할 것입니다.

  안쪽 for문이 s부터 e까지 순회합니다.

  첫 번째 if문에서 arr의 j번째 원소가 min보다 작고, k보다 arr의 j번째 원소가 크다면 arr의 j번째 원소를 min에 할당하여 갱신해나갑니다.

  두 번째 if문에서 min이 Integer 클래스의 MAX_VALUE가 아니라면 앞선 과정에서 min 값이 갱신되었다는 뜻입니다. 따라서 answer의 i번째 원소에 min을 할당하여 조건을 충족하면서 가장 작은 원소를 갖도록 합니다.

  아니라면 min이 Integer 클래스의 MAX_VALUE라는 것입니다. 값이 갱신되지 않았으므로, 조건에 충족하는 원소가 없었다는 뜻입니다. 따라서 답이 존재하지 않으므로 answer의 i번째 원소에 -1을 할당합니다.

 

  이 문제에서 자꾸 런타임 에러가 발생하기에 무엇인가 했더니, k가 범인이었습니다. k를 비교할 때 꼼꼼히 확인해야 할 것 같습니다. k는 arr의 원소가 아닙니다.