K번째 수 - 프로그래머스 (Java, Level 1)

 

package programmers;

import java.util.Arrays;
import java.util.PriorityQueue;

public class K번째수 {

	//priority queue활용
	public void solution(int[] array, int[][] commands) {
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		int[] answer = new int[commands.length];
		int index = 0;
		for(int i=0; i<commands.length; i++) {
			for(int j=commands[i][0]-1; j<commands[i][1]; j++) {
				pq.add(array[j]); 
			}//for end
			while(index<commands[i][2]-1) {
				pq.poll();
				index++;
			}//while end
			answer[i] = pq.poll();
			
			pq.clear();
			index = 0;
		}//for end

	}//solution() end
	
   	 //정렬 풀이
	public static void solutionSort(int[] array, int[][] commands) {
		int[] answer = new int[commands.length];
		int[] temp = null;
		int index = 0;
		
		for(int i=0; i<commands.length; i++) {
			int m = commands[i][1]-commands[i][0]+1;
			//해당 command에서 추출되는 요소의 수 크기의 배열 생성
			temp = new int[m];
			//조건에 맞는 요소 대입하여 새 배열 만듬
			for(int j=commands[i][0]-1; j<commands[i][1]; j++) {
				temp[index++] = array[j];
			}//for end
			
			//index 초기화
			index = 0;
			
			//새 배열 정렬 
			//Arrays.sort(temp);
			sort(temp, 0, m-1);
			
			//정렬된 새 배열에서 k번째 수
			answer[i] = temp[commands[i][2]-1];
			
		}//for end
		
		for(int num : temp) {
			System.out.print(num+" ");
		}//for end
	}//soㅣutionSort() end
	
	//퀵 정렬 구현
	void sort(int[] array, int left, int right) {
		int pl = left;
		int	pr = right;
		int x = array[(pl+pr)/2];
		
		do {
			while(array[pl] < x) pl++;
			while(array[pr] > x) pr--;
			if(pl<=pr) {
				int temp = array[pl];
				array[pl++] = array[pr];
				array[pr--] = temp;
			}//if end
		} while(pl<=pr); //do-while end
		
		if(left<pr) sort(array, left, pr);
		if(pl<right) sort(array, pl, right);
	}//sort() end
}

 

**

퀵 정렬 구현