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

 

https://school.programmers.co.kr/learn/courses/30/lessons/181923

프로그래머스

 

문제

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

---

내가 오답이였던 이유

저 i가 arr[i] 라는 것은 i의 인덱스 즉, 배열을 도는 for문의 범위가, s와 e만큼 index를 돈다는 의미이다.

입출력을 예로 들면

이차원 배열의 첫번째 1열은 0~4, 2열은 0~3, 3열은 0~2인데, 이것을 잘못 이해해서, 모든 이차원 배열의 열 하나하나 전부 인덱스를 for문으로 돌리다보니, 시간 초과라는 결과가 발생했다.

답을 보고, 문제를 다시 보니 내가 바보였다.

기존 오답 코드

class Solution {
    public int[] solution(int[] arr, int[][] queries) {
        int[] answer = new int[queries.length];
        for(int i = 0; i < queries.length; i++){
            int num = queries[i][2];
            for(int j = 0; j < arr.length; i++){
                if (arr[j] > num){
                    answer[i] = Math.min(answer[i], arr[j]); 
                }
            }
            
        }
        return answer;
    }
}

 

정답 코드

import java.util.*;
class Solution {
    public int[] solution(int[] arr, int[][] queries) {
        int[] answer = new int[queries.length];
        Arrays.fill(answer,Integer.MAX_VALUE);
        for(int i = 0; i < queries.length; i++){
            int s = queries[i][0];
            int e = queries[i][1];
            int k = queries[i][2];
            
            for(int j = s; j <= e; j++){
                if (arr[j] > k){
                    answer[i] = Math.min(answer[i], arr[j]);
                }
            }
            if(answer[i] == Integer.MAX_VALUE)
                answer[i] = -1;
        }
        return answer;
    }
}

 

생각해보니, 최소값을 구하기 위해

자바 util에 Arrays 라이브러리에 채우는 fill 함수와, 

Integer.MAX_VALUE는 java.lang 패키지의 Java Integer 클래스 에 있는 숫자를 사용했다.

아직은 자바로 값 표현이 익숙치 않다.

매번 c++로 그냥 999999 대충 int 범위만큼 때리던 못된 습관이 있었다. 낼은 삼항 연산자를 써서 다시 풀어봐야겠다 ,,