[Java] 백준 11004 K번째 수 - 퀵 정렬

백준 11004 K번째 수
문제

수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오.
입력

첫째 줄에 N(1 ≤ N ≤ 5,000,000)과 K (1 ≤ K ≤ N)이 주어진다.

둘째에는 A1, A2, ..., AN이 주어진다. (-10^9 ≤ Ai ≤ 10^9)

출력

A를 정렬했을 때, 앞에서부터 K번째 있는 수를 출력한다.

---

제출

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(in.readLine());
		int[] A = new int[N];
		for (int i = 0; i < N; i++) {
			A[i] = Integer.parseInt(st.nextToken());
		}
		quickSort(A, 0, N -1, K -1);
		System.out.println(A[K - 1]);
	}
	public static void quickSort(int[] A, int S, int E, int K) {
		if (S < E) {
			int pivot = partition(A, S, E);
			if (pivot == K)
				return;
			else if (K < pivot)
				quickSort(A, S, pivot -1, K);
			else
				quickSort(A, pivot + 1, E, K);
		}
	}
	public static int partition(int[] A, int S, int E) {
		if (S + 1 ==E) {
			if(A[S] > A[E])swap(A, S, E);
			return E;
		}
		int M = (S + E) / 2;
		swap(A, S, M);
		int pivot = A[S];
		int i = S + 1, j = E;
		while(i <= j) {
			while (pivot < A[j] && j > 0) {
				j--;
			}
			while (pivot > A[i] && i < A.length-1) {
				i++;
			}
			if (i <= j) {
				swap (A, i++, j--);
			}
		}
		A[S] = A[j];
		A[j] = pivot;
		return j;
	}
	private static void swap(int[] A, int i, int j) {
		int temp = A[i];
		A[i] = A[j];
		A[j] = temp;
		
	}
}

예제

5 2
4 1 2 3 5

결과

백준 11004 K번째 수

11004번: K번째 수