11004번 K번째 수 (Java)

문제 설명

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

제한 조건

• 시간제한 : 1초
• 메모리제한 : 256MB

입력 설명

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

둘째에는 A₁, A₂, …, A_N이 주어진다. (-10⁹ ≤ A_i ≤ 10⁹)

출력 설명

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

예제 입력 및 출력1

5 2
4 1 2 3 5

---

2

나의 풀이 (quick sort 직접구현, 시간초과)

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int arrLength = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        
        int[] arr = new int[arrLength];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<arrLength; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        quickSort(arr, 0, arrLength-1, k-1);
        System.out.println(arr[k-1]);
    }
    
    static void quickSort(int[] arr, int start, int end, int k){
        if(start < end) {
            // 기준점 구하기
            int pivot = divideAndSort(arr, start, end);
            if(pivot == k){
                // 값 일치, 종료
                return;
            } else if (k < pivot){
                // 원하는 값의 인덱스가 기준점보다 작으므로 기준점 기준 왼쪽으로 진행
                quickSort(arr, start, pivot-1, k);
            } else {
                // 원하는 값의 인덱스가 기준점보다 크므로 기준점 기준 오른쪽으로 진행
                quickSort(arr, pivot+1, end, k);
            }
        }    
    }
    
    static int divideAndSort(int[] arr, int start, int end){
        int mid = (start + end) / 2;
        swap(arr, start, mid);
        
        int pivot = arr[start];
        int i = start;
        int j = end;
        while(i < j) {
            while(pivot < arr[j]){
                // 기준점보다 작은 수가 나올때까지 이동
                j--;
            }
            
            while(i < j && pivot >= arr[i]){
                // 기준점보다 큰 수가 나올 때까지 이동
                i++;
            }
            swap(arr, i, j);
        }
        arr[start] = arr[i];
        arr[i] = pivot;
        return i;
    }
   
    static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

나의 풀이 (Arrays.sort() 사용)

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int arrLength = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        
        int[] arr = new int[arrLength];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<arrLength; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        Arrays.sort(arr);
        System.out.println(arr[k-1]);
    }
}

퀵소트를 직접 구현하니 시간초과가 떴다. (???)

자바에서 제공하는 java.util.Arrays 클래스의 sort() 메소드 또한 quick sort 기반으로 구현된것으로 알고있는데..

잘못 구현한건가? 다시 수정해봐야겠다.