[프로그래머스] K번째 수

자바에서는 한번 만든 배열을 초기화 하기가 어렵기 때문에 temp라는 배열을 만들어 필요한 부분에만 array 배열의 값을 복사해주었다.

그리고 quickSort를 사용해서 복사 받은 부분만을 정렬해주고 해당하는 순서에 있는 temp의 값을 가져와 answer에 넣어 줬다.

 

사용된 quickSort를 자세히 알고 싶다면 추천하는 유튜브 강의이다.  https://www.youtube.com/watch?v=7BDzle2n47c&t=474s

위의 강의를 보고 quickSort를 이해했고 배열을 필요한 부분만 뽑아 올 수 있다면 어렵지 않게 풀 수 있을거라 생각한다.

 

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        int[] temp = new int[100];
        
        for(int i=0; i<commands.length; i++){
            for(int j=commands[i][0]-1;j<commands[i][1]; j++){
                temp[j]=array[j];
            }
            quickSort(temp,commands[i][0]-1,commands[i][1]-1);
            answer[i]=temp[commands[i][2]+commands[i][0]-2];
        }
        printArr(answer);
        return answer;
    }
    
    public static void quickSort(int[] arr) {
		quickSort(arr,0,arr.length-1);
	}

	public static void quickSort(int[] arr, int start, int end) {
		int part2 = partition(arr,start,end);
		if(start<part2-1) {
			quickSort(arr,start,part2-1);
		}
		if(end>part2) {
			quickSort(arr,part2,end);
		}
	}

	public static int partition(int[] arr, int start, int end) {
		int pivot = arr[(start+end)/2];
		while(start<=end) {
			while(arr[start]<pivot) start++;
			while(arr[end]>pivot) end--;
			if(start<=end) {
				swap(arr,start,end);
				start++;
				end--;
			}
		}
		return start;
	}
	
	public static void printArr(int[] arr) {
		for (int data : arr) {
			System.out.print(data+", ");
		}
		System.out.println();
	}
	
	public static void swap(int[] arr, int start, int end) {
		int temp=arr[start];
		arr[start]=arr[end];
		arr[end]=temp;
	}
}