문제

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

입력

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

둘째에는 A1, A2, ..., AN이 주어진다. (-109 ≤ Ai ≤ 109)

출력

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

풀이

해당 문제는 정렬된 배열 A에서 K번째 수를 찾아 출력하는 문제이다.

일반적으로 배열을 정렬한 뒤 K번째 수를 출력하려고 할텐데, 시간초과가 나올 것이다. 그래서 생각해 본 것이 이진탐색이다. 다른 분들의 풀이는 퀵정렬을 많이 사용했다. 또한 Scanner를 사용하면 시간초과가 발생하여 BufferedReader를 사용하였다.

이진탐색을 어떻게 사용하면 되는 것인가? 이진탐색을 할 때 시작점, 끝점, 중앙점을 이용한다. 이때 중앙점과 K를 비교하는 방식으로 구현하면 된다.

왜냐하면 일단 이진탐색은 O(logN)의 시간복잡도를 가져서 매우 빠르게 진행하며 중앙점과 찾고자하는 K가 같으면 해당 인덱스의 값을 그대로 출력하면 된다. K가 중앙점보다 작을 때 범위는 다시 start ~ mid-1 로 줄어들어 다시 찾으면 되고 반대로 클 때 mid+1 ~ end 범위로 찾으면 된다. 따라서 불필요한 부분은 찾지 않아도 되어 찾는 시간이 매우 빨라짐을 알 수 있다.

소스

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

public class Main {
	public static int binarySearch(ArrayList<Integer> arr, int target, int start, int end) {
		if (start > end) {
			return -1;
		}

		int mid = (start + end) / 2;
		if (target == mid) {
			return mid;
		} else if (target < mid) {
			return binarySearch(arr, target, start, mid - 1);
		} else {
			return binarySearch(arr, target, mid + 1, end);
		}

	}

	public static void main(String[] args) throws IOException {
		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());

		ArrayList<Integer> arr = new ArrayList<Integer>();
		st = new StringTokenizer(br.readLine(), " ");
		while (st.hasMoreTokens()) {
			arr.add(Integer.parseInt(st.nextToken()));
		}

		Collections.sort(arr);

		System.out.println(arr.get(binarySearch(arr, k - 1, 0, n - 1)));

		br.close();
	}

}