[백준 11004] K번째 수

 

퀵정렬로 정렬하여 k-1 의 인덱스를 출력했는데 96%에서 계속 시간초과가 났다.

질문게시판을 보니 퀵정렬 대신 퀵셀렉트를 써야된다고 한다.

 

퀵셀렉트는 퀵정렬 도중 원하는 인덱스를 바로 캐치하는 알고리즘인데, 공부할 것도 많은데 알아보기 귀찮았다.

 

그래서 합병정렬로 해봤는데 역시나 풀린다....

 

'잘' 구현할거 아니면 퀵정렬보다는 합병정렬 쓰는걸 추천한다.

 

 

public class Main {
    
    static int temp[];
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int a[] = new int[n];
        temp = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++)
            a[i] = Integer.parseInt(st.nextToken());
        
        divide(a, 0, n-1);
        
        bw.write(a[k-1] + "");
        bw.flush();
        bw.close();
    }
    
    public static void divide(int a[], int left, int right) {
        int mid = (left + right)/2;
        
        if(left < right) {
            divide(a, left, mid);
            divide(a, mid+1, right);
            merge(a, left, mid, right);
        }
    }
    
    public static void merge(int a[], int left, int mid, int right) {
        int leftFirst = left;
        int rightFirst = mid+1;
        
        int leftIndex = left;
        while(leftFirst <= mid && rightFirst <= right) {
            if(a[leftFirst] <= a[rightFirst])
                temp[leftIndex++] = a[leftFirst++];
            else
                temp[leftIndex++] = a[rightFirst++];
        }
        
        if(leftFirst > mid) {
            for(int i=rightFirst; i<=right; i++)
                temp[leftIndex++] = a[i];
        } else {
            for(int i=leftFirst; i<=mid; i++)
                temp[leftIndex++] = a[i];
        }
        for(int i=left; i<=right; i++)
            a[i] = temp[i];
    }
}