1. 문제

2. 아이디어

• 퀵 정렬 혹은 병합 정렬을 사용

3. 코드

3.1 퀵 정렬

import java.util.*;
import java.io.*;

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 N = Integer.parseInt(st.nextToken());
    int K = Integer.parseInt(st.nextToken());

    int[] arr = new int[N];
    st = new StringTokenizer(br.readLine());
    for ( int i = 0; i<N;i++){
      arr[i] = Integer.parseInt(st.nextToken());
    }
    QuickSorter.quickSort(arr);
    System.out.println(arr[K-1]);
  } 
} // Main Class End

class QuickSorter{

  public static void quickSort(int[] arr){
    sort(arr, 0, arr.length -1);
  } // 1. quickSort end

  public static void sort(int[] arr, int low, int high){
    if (low >= high) return;

    int mid = partition(arr, low, high);
    sort(arr, low, mid -1);
    sort(arr, mid, high);
  } // 2. sort end

  public static void swap(int[] arr, int i, int j){
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
  } // 3. swap end

  public static int partition(int[] arr, int low, int high){
    int pivot = arr[(low + high) / 2];

    while(low <= high){
      while (arr[low] < pivot) low ++;
      while (arr[high] > pivot) high --;

      if(low <= high){
        swap(arr, low, high);
        low ++;
        high --;
      }
    } // first while end

  return low;
  } // 4. partition end
} // QuickSorter Class end

3.2 병합 정렬

import java.util.*;
import java.io.*;
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 N = Integer.parseInt(st.nextToken());
    int K = Integer.parseInt(st.nextToken());

    st= new StringTokenizer(br.readLine());
    int[] arr = new int[N];

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

    MergeSorter.mergeSort(arr);
    System.out.println(arr[K-1]);
    
  } 
}

class MergeSorter{
  public static void mergeSort(int[] arr){
    sort(arr, 0, arr.length);
  } // mergeSort

  public static void sort(int[] arr, int low, int high){
    if(high - low < 2) return;

    int mid = (high + low) / 2;
    sort(arr, low, mid);
    sort(arr, mid, high);
    merge(arr, low, mid, high);
  } // sort

  public static void merge(int[] arr, int low, int mid, int high){
    int[] tmp = new int[high - low];
    int l = low;
    int h = mid;
    int j = 0;

    while(l < mid && h < high){
      if(arr[l] < arr[h]){
        tmp[j] = arr[l];
        l ++;
        j ++;
      }
        
      else{
        tmp[j] = arr[h];
        h ++;
        j ++;
      }
      
    } // while end

    while (l < mid){
      tmp[j] = arr[l];
      l ++;
      j ++;
    }

    while (h < high){
      tmp[j] = arr[h];
      h ++;
      j ++;
    }

    for(int i = low; i < high; i++){
      arr[i] = tmp[i - low];
    }
    
  } // merge end
  
} // 1. MergeSorter class end

4. 배운점

• 파이썬으로도 구현을 해보았는데 같은 로직임에도 파이썬에서는 timeout 오류가 생긴다.
• 좀 더 효율적인 방법을 생각하는 것이 필요