11004번 'K번째 수'

학교에서 들은 거다! 해서 이진탐색을 응용해서 풀려고 했는데 시간초과가 난다.

C++에는 K번째 수를 구하는 함수가 STL에 아예 있나보다...

퀵소트를 응용한 퀵서치 알고리즘이란게 있어서 학교에서 배운 퀵소트 코드를 일단 그대로 갖다박아서 풀었는데도 시간초과가 난다.

인터넷에 있는 소스를 그대로 Java로 고쳐쓰기만 했는데 시간초과........

못풀었다.

import java.io.*;

import java.util.*;

class Main {

public static void main(String[] args) throws IOException {

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

String[] firstLine = in.readLine().split(" ");

String[] secondLine = in.readLine().split(" ");

int n = Integer.parseInt(firstLine[0]);

int k = Integer.parseInt(firstLine[1]);

int[] array = new int[n];

for(int i=0; i<n; ++i) {

array[i] = Integer.parseInt(secondLine[i]);

}

Arrays.sort(array);

//k번째 수

System.out.println(binarySearch(array, k - 1));

}

static int binarySearch(int[] array, int k) {

int lowIndex = 0;

int highIndex = array.length - 1;

int middleIndex = (lowIndex + highIndex) / 2;

while(middleIndex != k) {

if(k < middleIndex) {

highIndex = middleIndex;

} else if(k > middleIndex) {

lowIndex = middleIndex;

k = k - middleIndex + 1;

}

middleIndex = (lowIndex + highIndex) / 2;

}

return array[middleIndex];

}

}

이진탐색.

import java.io.*;

import java.util.*;

class Main {

public static void main(String[] args) throws IOException {

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

String[] firstLine = in.readLine().split(" ");

String[] secondLine = in.readLine().split(" ");

int n = Integer.parseInt(firstLine[0]);

int k = Integer.parseInt(firstLine[1]);

int[] array = new int[n];

for(int i=0; i<n; ++i) {

array[i] = Integer.parseInt(secondLine[i]);

}

//k번째 수

System.out.println(quickSort(array, 0, n - 1, k - 1));

}

static int binarySearch(int[] array, int k) {

int lowIndex = 0;

int highIndex = array.length - 1;

int middleIndex = (lowIndex + highIndex) / 2;

while(middleIndex != k) {

if(k < middleIndex) {

highIndex = middleIndex;

} else if(k > middleIndex) {

lowIndex = middleIndex;

k = k - middleIndex + 1;

}

middleIndex = (lowIndex + highIndex) / 2;

}

return array[middleIndex];

}

static int quickSort(int[] list, int left, int right, int k) {

if(left < right) {

int pivot = partition(list, left, right);

if(k < pivot) {

return quickSort(list, left, pivot - 1, k);

} else if(k > pivot) {

k = k - pivot + 1;

return quickSort(list, pivot + 1, right, k);

} else {

return list[pivot];

}

} else {

return -1;

}

}

static int partition(int[] list, int left, int right) {

int pivot, low, high;

low = left;

high = right + 1;

pivot = list[left];

do {

do {

++low;

} while(low <= high && list[low] < pivot);

do {

--high;

} while(high >= left && list[high] > pivot);

if(low < high) {

int temp = list[low];

list[low] = list[high];

list[high] = temp;

}

} while(low < high);

int temp = list[left];

list[left] = list[high];

list[high] = temp;

return high;

}

}

퀵서치.