[프로그래머스/Java] K번째수 : Arrays.copyOfRange()

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

프로그래머스

 

★ Queue를 초기화하지 않으면 찌꺼기 데이터가 들어갈 수 있음

1. for문이 시작하자마자 큐를 매번 새로 만들어주거나(queue = new PriorityQueue<>();)

2. 루프가 끝날 때 큐를 비워주(queue.clear();)

 

★ 정답의 배열의 크기를 아는 상황에서는 stream() 대신 일반배열 쓰기! (효율성 테스트)

 

import java.util.*;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        ArrayList<Integer> list = new ArrayList<>();
        
        for(int cnt=0; cnt<commands.length; cnt++){
            PriorityQueue<Integer> queue = new PriorityQueue<>();
            
            int i = commands[cnt][0]-1;
            int j = commands[cnt][1]-1;
            int k = commands[cnt][2]-1;

            for(int num = i; num<=j; num++){
                queue.offer(array[num]);
            }
            
            while(k>0){
                k--;
                queue.poll();
            }
            list.add(queue.poll());
        }
        
        return list.stream().mapToInt(i->i).toArray();
    }
}

 

 

★ Arrays.copyOfRange()  : 자바가 제공하는 배열 자르기 메서드

1. 가독성

2. 압도적인 성능차이

3. 인덱스 계산의 단순

import java.util.Arrays;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        // 1. 정답을 담을 배열을 commands 개수만큼 미리 만듭니다.
        int[] answer = new int[commands.length];
        
        for (int cnt = 0; cnt < commands.length; cnt++) {
            int i = commands[cnt][0];
            int j = commands[cnt][1];
            int k = commands[cnt][2];
            
            // 2. [핵심] array의 i-1번째부터 j번째 직전까지 슥삭 잘라냅니다.
            // (i-1은 포함, j는 미포함이라 딱 문제 조건만큼 잘립니다.)
            int[] slicedArray = Arrays.copyOfRange(array, i - 1, j);
            
            // 3. 잘라낸 배열을 오름차순으로 정렬합니다. (듀얼 피벗 퀵소트라 엄청 빠릅니다.)
            Arrays.sort(slicedArray);
            
            // 4. 정렬된 배열에서 k-1 번째 수를 정답 배열에 바로 꽂아 넣습니다.
            answer[cnt] = slicedArray[k - 1];
        }
        
        return answer;
    }
}