문제
정수 배열 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
class Solution {
public int[] solution(int[] arr, int[][] queries) {
int[] answer = new int[queries.length];
int idx = 0;
for(int q = 0; q < queries.length; q++) {
answer[q] = 1000001;
for(int i = queries[q][0]; i <= queries[q][1]; i++) {
if(arr[i] > queries[q][2]) {
answer[q] = Math.min(answer[q], arr[i]);
}
}
if(answer[q] == 1000001) {
answer[q] = -1;
}
} // Arrays.fill() 사용도 고려
return answer;
}
}k보다 큰 수들 중 최솟값을 찾는 문제라서, 제한조건에 따라 1,000,000보다 살짝 큰 1,000,001 을 각 answer 원소의 시작값으로 지정하였다.
그 후 만약 각 쿼리의 구간을 순회하면서 k보다 큰 경우라면 answer의 원소와 현재 순회중인 값과 비교해서 작은 값을 찾아 교체한다. 어짜피 이 작업은 무조건 k보다 큰 경우에 한해 실행되며, 그 중 제일 작은 값을 찾는 문제이니 문제될건 없다.
각 쿼리의 작업이 끝날 때 마다 처음 설정한 값 1,000,001 이 그대로라면 교체할 값이 없었다는 뜻이되므로 -1로 설정한다.
그런데 이 작업 없이 처음부터 배열을 -1로 초기화하면 어떨까 싶었다.
Arrays.fill(answer, -1) 이라고 하면 answer의 원소를 -1로 초기화 하는것이였다.
하지만 이는 O(n) 이란 시간복잡도가 생긴다.
그런것을 고려하면 내가 한 방법이 좀 더 효율적이지 않을까 라는 생각이 든다.
출처
https://school.programmers.co.kr/learn/courses/30/lessons/181923