[백준 온라인 저지] 24060. 알고리즘 수업 - 병합 정렬 1

1. 입력

- 첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 500,000), 저장 횟수 K(1 ≤ K ≤ 10^8)가 주어진다.

- 다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 10^9)

 

2. 출력

- 병합 정렬을 진행할 때 배열 A에 K 번째 저장 되는 수를 출력한다. 저장 횟수가 K 보다 작으면 -1을 출력한다.

 

3. 코드

import java.util.*;
import java.io.*;
class Main {
    static int count = 0;
    static int val = -1;
    static int k;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer token = new StringTokenizer(br.readLine());
        int n = Integer.valueOf(token.nextToken());
        k = Integer.valueOf(token.nextToken());
        int[] A = new int[n];
        token = new StringTokenizer(br.readLine());
        for(int i=0 ; i<n ; i++)
            A[i] = Integer.valueOf(token.nextToken());
        merge_sort(A, 0, n-1);
        System.out.print(val);
    }
    
    static void merge_sort(int[] A, int p, int r){
        if(p<r){
            int q = (p+r)/2;
            merge_sort(A, p, q);
            merge_sort(A, q+1, r);
            merge(A, p, q, r);
        }
    }
    
    static void merge(int[] A, int p, int q, int r){
        int i = p, j = q+1, t = 0;
        int[] tmp = new int[r-p+1];
        while(i<=q && j<=r){
            if(A[i]<=A[j])
                tmp[t++] = A[i++];
            else
                tmp[t++] = A[j++];
        }
        while(i<=q)
            tmp[t++] = A[i++];
        while(j<=r)
            tmp[t++] = A[j++];
        i = p; t = 0;
        while(i<=r){
            A[i++] = tmp[t];
            count++;
            if(count==k)
            	val = tmp[t];
            t++;
        }
    }
}