[프로그래머스] 정렬 Level 1. K번째수(JAVA)

 

자르고, 정렬하고, 뽑고 끝!

 

코드

import java.util.*;
class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        int[] copyArray = {};
        for(int i = 0; i < commands.length; i++){
            int[] command = commands[i];
            copyArray = Arrays.copyOfRange(array, command[0]-1, command[1]);
            Arrays.sort(copyArray);
            answer[i] = copyArray[command[2]-1];
        }
       return answer;
    }
}

 

결과

---

자바 내장함수를 사용했더니 너무 금방 끝나버려서 직접 구현 해봤다.

copyOfRange 함수 만든김에 정렬은 merge sort 썼음

로직은 동일함

 

코드

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        int[] newArray = {};
        for(int i = 0; i < commands.length; i++){
            int[] command = commands[i];
            newArray = copyOfRange(array, command[0]-1, command[1]);
            newArray = mergeSort(newArray);
            answer[i] = newArray[command[2]-1];
        }
       return answer;
    }
    
    public int[] copyOfRange(int[] array, int startIndex, int endIndex){
        int arrayLength = endIndex-startIndex;
        int[] copyArray = new int[arrayLength];
        for(int i = 0; i < arrayLength; i++){
            copyArray[i] = array[i+startIndex];
        }
        return copyArray;
        
    }
    
    public int[] mergeSort(int[] array){
        if (array.length < 2) return array;
        int arrayLength = array.length;
        int[] lowArray = mergeSort(copyOfRange(array, 0, array.length/2));
        int[] highArray = mergeSort(copyOfRange(array, array.length/2, array.length));
        int[] mergeArray = new int[array.length];
        int low = 0;
        int high = 0;
        int merge = 0;
        while(low < lowArray.length && high < highArray.length){
            if(lowArray[low] < highArray[high])
                mergeArray[merge++] = lowArray[low++];
            else
                mergeArray[merge++] = highArray[high++];
        }
        while(low < lowArray.length){
            mergeArray[merge++] = lowArray[low++];
        }
        while(high < highArray.length){
            mergeArray[merge++] = highArray[high++];
        }
        return mergeArray;
    }
}

결과

...?

??????

왜 내장함수 썼을때보다 10배나 빨라졌을까???

Arrays.sort() 함수도 내부적으로는 quick sort나 merge sort 기반이라고 하던데?