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

🧐 문제 이름

수열과 구간 쿼리 2

 

 

🧾 문제 설명

정수 배열 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 : [0, 1, 2, 4, 3] 
• queries : [[0, 4, 2],[0, 3, 2],[0, 2, 2]]
• return : [3, 4, -1]

첫 번째 쿼리의 범위에는 0, 1, 2, 4, 3이 있으며 이 중 2보다 크면서 가장 작은 값은 3입니다.
두 번째 쿼리의 범위에는 0, 1, 2, 4가 있으며 이 중 2보다 크면서 가장 작은 값은 4입니다.
세 번째 쿼리의 범위에는 0, 1, 2가 있으며 여기에는 2보다 큰 값이 없습니다.
따라서 [3, 4, -1]을 return 합니다.

 

---

☑️ 문제 풀이

 

📍 해결 방법 1 - ArrayList만 사용

 

코드가 조금 복잡해지긴 했지만, 일단 나는 어떻게 풀었냐면,

 

1. for-each문을 통해 queries의 행들을 query로 받는다.

2. 이중 for문을 이용해 인덱스 query[0]부터 query[1]에 해당하는 arr값들을 query[2]와 비교해 크면 일단 ArrayList에 add한다.

3. ArrayList가 비었다면 -1을, 들어있다면 가장 작은 값을 Collections.min(arrayList)을 이용해 answer에 추가한다.

 ⇒ 이 과정에서 import java.util.Collection; 추가 안해줘서 에러 났다;; (인텔리제이야 고마워)

4. ArrayList를 int[]로 변환해주면 끝난다.

 

import java.util.ArrayList;
import java.util.Collections;

class Solution {
    public int[] solution(int[] arr, int[][] queries) {
        
        ArrayList<Integer> answer = new ArrayList<>();
        
        for (int[] query : queries) {
            
            ArrayList<Integer> list = new ArrayList<>();
            
            for (int i = query[0]; i <= query[1]; i++) {
                if (arr[i] > query[2]) {
                    list.add(arr[i]);
                }
            }
            
            if (list.isEmpty()) {
                answer.add(-1);
            } else {
                answer.add(Collections.min(list));
            }
        }
        
        int[] intArray = new int[answer.size()];
        
        for (int i = 0; i < answer.size(); i++) {
            intArray[i] = answer.get(i);
        }
        
        return intArray;
    }
}

 

문제 풀면서 꽤 고민을 많이 했고, 확인 했을  때 실패도 몇 번 나왔다. 'queries[2]보다 큰 수 중에서 가장 작은 수'를 어떻게 해결해야 하나 고민이 있었다. 

 

ArrayList로 풀면 되지만, 그렇게 풀면 다시 int[]로 변환하면서 코드가 길어질 것 같아 더 간단한 답을 찾고 싶어 머리 쥐어짜다가 그냥 ArrayList로 풀었다.

 

📍 해결 방법 2 - fill, 삼항 연산자

 

1. 이분은 Arrays.filll()메서드를 이용해서 answer를 모두 -1로 채웠다.

2. 그 후에 if문을 이용해 query[2]와 answer[idx] 값을 비교한다.

3. answer값이 더 크다면, 그 중에서 가장 작은 값을 찾기 위해 삼항 연산자를 이용한다. 

 ⇒ answer[idx] = answer[idx] == -1 ? arr[i] : Math.min(answer[idx], arr[i]);

 

풀이방법 보면서 감탄했다. 처음부터 -1로 채운 후에 -1이면 넣고, 아니면 더 작은 값을 넣는다.

그리고 Array.fill 메소드도 처음 알아서 유용한 풀이법인 것 같다.

 

import java.util.Arrays;

class Solution {
    public int[] solution(int[] arr, int[][] queries) {

        int[] answer = new int[queries.length];
        Arrays.fill(answer, -1);

        for (int idx = 0; idx < queries.length; idx++) {
            int[] query = queries[idx];
            int s = query[0], e = query[1], k = query[2];

            for (int i = s; i <= e; i++) {
                if (k < arr[i]) {
                    answer[idx] = answer[idx] == -1 ? arr[i] : Math.min(answer[idx], arr[i]);
                }
            }

        }

        return answer;
    }
}

 

📍 해결 방법 3 - Stream

 

이렇게 완전 깔끔한 Stream을 통해 푸신 분도 계셨다. 난 아직 stream을 제대로 쓸 줄 몰라서.. 더 공부한 뒤에 stream으로 풀어봐야 할 것 같다.

 

import java.util.stream.IntStream;

class Solution {
    public int[] solution(int[] arr, int[][] queries) {
        int[] answer = {};
        return IntStream.range(0, queries.length)
                .map(q -> IntStream.rangeClosed(queries[q][0], queries[q][1])
                        .map(i -> arr[i])
                        .filter(i -> i > queries[q][2])
                        .min().orElse(-1)
                ).toArray();
    }
}