[자바] 프로그래머스 - 수열과 구간 쿼리 2 (Lv0, Java)

목차

문제 : Programmers - 수열과 구간 쿼리 2

문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

 

 

필요 알고리즘

• 구현
  
  • 문제에서 제시된 대로 구현해주면 됩니다.

 

 

풀이

  arr[s], arr[s+1], ... , arr[e-1], arr[e] 중 k보다 큰 값들 중 가장 작은 값을 찾는 문제이다.

문제만 잘 이해했다면 반복문을 잘 사용해서 풀 수 있다.

k보다 큰 값 중 '가장 작은 값'이 문제일 수 있는데, 애초에 나올 수 있는 수치보다 큰 값을 무한대로 정하고 그 값을 갱신하면서 진행하면 편하다. 이 문제의 경우 0 ≤ arr의 원소 ≤ 1,000,000 이므로 1000001 이상으로 잡으면 된다. 아니면 그냥 Integer.MAX_VALUE로 해도 상관없으나, 차후 문제를 풀다보면 MAX_VALUE로 잡으면 오버플로우가 날 위험이 있어서 문제에서 제시된 최대치를 초과하는 가장 작은 값을 무한대로 잡는 습관이 의외로 도움된다.

 

 

코드 : github

/**
 * 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
 */
class Solution {
    private static final int INF = 1000001;

    public int[] solution(int[] arr, int[][] queries) {
        int[] answer = new int[queries.length];
        int idx = 0;

        for (int[] query : queries) {
            int s = query[0];
            int e = query[1];
            int k = query[2];

            int result = INF;
            for (int i = s; i <= e; i++) {
                if (arr[i] <= k || arr[i] >= result) continue;

                result = arr[i];
            }

            answer[idx++] = result == INF ? -1 : result;
        }

        return answer;
    }
}