[알고리즘] 11004번

오늘 풀어볼 문제는 백준 11004번 문제 "K번째 수" 이다.

이 문제는 실버5 문제이고 퀵 정렬 문제이다.

문제

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

입력

첫째 줄에 N(1 ≤ N ≤ 5,000,000)과 K (1 ≤ K ≤ N)이 주어진다.
둘째에는 A1, A2, ..., AN이 주어진다. (-109 ≤ Ai ≤ 109)

출력

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

📌첫 번째 도전📌
이 문제는 퀵정렬을 활용해서 정렬 후 K번째 수를 찾아내면 된다.

public class Main {
    static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());

        arr = new int[N];

        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        quickSort(arr);

        System.out.println(arr[K-1]);
    }
    public static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(int[] arr, int start, int end) {
        if (start >= end)
            return;

        int pivot = start;
        int lo = start + 1;
        int hi = end;

        while (lo <= hi) {
            while (lo <= end && arr[lo] <= arr[pivot])
                lo++;
            while (hi > start && arr[hi] >= arr[pivot])
                hi--;
            if (lo > hi)
                swap(arr, hi, pivot);
            else
                swap(arr, lo, hi);
        }

        quickSort(arr, start, hi - 1);
        quickSort(arr, hi + 1, end);
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

하지만.. 시간 초과가 떠버렸다.. 더 빠른 속도로 정렬을 해야하나 보다.

📌두 번째 도전📌

public class Main {
    static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());

        arr = new int[N];

        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        quickSort(arr);

        System.out.println(arr[K-1]);
    }
    private static void quickSort(int[] arr){
        quickSort(arr, 0, arr.length - 1);
    }

    private 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(part2 < end){
            quickSort(arr, part2, end);
        }
    }

    private 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;
    }

    private static void swap(int[] arr, int start, int end){
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
    }
}

[문제출처] https://www.acmicpc.net/problem/11004