[프로그래머스](lv.1) K번째 수 (java)

<문제>

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

<나의 풀이>

import java.util.Arrays;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        // 1. 값 받기
        int[] answer = new int[commands.length];	// 정답을 담아줄 배열
       
        for (int i=0; i< commands.length; i++){
            int start = commands[i][0];	// 잘라줄 배열의 시작 위치
            int end = commands[i][1];	// 잘라줄 배열의 끝 위치
            int k = commands[i][2];	// 잘린 배열에서 뽑을 숫자의 위치
            // 2. 배열 자르기
            int[] target = Arrays.copyOfRange(array, start-1, end);
            // 3. 정렬
            Arrays.sort(target);
            // 4. k번째 수 추출 후 정답에 삽입
            answer[i] = target[k-1];
        }
        return answer;
    }
}

<다른 사람의 풀이>

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int n = 0;
        int[] ret = new int[commands.length];

        while(n < commands.length){
            int m = commands[n][1] - commands[n][0] + 1;

            if(m == 1){
                ret[n] = array[commands[n++][0]-1];
                continue;
            }

            int[] a = new int[m];
            int j = 0;
            for(int i = commands[n][0]-1; i < commands[n][1]; i++)
                a[j++] = array[i];

            sort(a, 0, m-1);

            ret[n] = a[commands[n++][2]-1];
        }

        return ret;
    }
	//   퀵 정렬
    void sort(int[] a, int left, int right){
        int pl = left;
        int pr = right;
        int x = a[(pl+pr)/2];

        do{
            while(a[pl] < x) pl++;
            while(a[pr] > x) pr--;
            if(pl <= pr){
                int temp = a[pl];
                a[pl] = a[pr];
                a[pr] = temp;
                pl++;
                pr--;
            }
        }while(pl <= pr);

        if(left < pr) sort(a, left, pr);
        if(right > pl) sort(a, pl, right);
    }
}

<핵심 개념>

자바는 파이썬처럼 인덱스 슬라이싱 개념이 없어서 Arrays의 copyOfRange(arr, start, end) 를 활용했다. copyOfRange의 end는 파이썬과 동일하게 포함되지 않는다.
정렬 문제라 정렬을 직접 구현해 봐야됐는데 문제를 시간내에 풀려고 하다보니 .sort() 함수를 사용했다. 그래도 sort 알고리즘을 직접 구현해보도록 하자.