1300 K 번째 수 (java)

N X N 의 2차원 배열을 오름차순 정렬하여 일차원 배열로 만들 었을 때에서 K번 째 수를 찾는 문제.

 

정답이 될 수 있는 최대 M, 최소 1를 이분탐색하여 정답을 찾는다.

 

이분 탐색한 mid 값이 정답인지 확인하는 과정이 중요하다.

 

1부터 N까지 for 루프 실행하면서 mid / i 가 크면 N 번째씩 뒤로 가고, N이 더 크면 mid / i 만큼 뒤로 간다.

 

-> 각 i 행마다 최댓값은 N * i이고, N만큼의 수가 있다. mid / i 가 최댓값이 아니라면 mid는 mid/i 번째의 수이다.

 

 

 

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int M = sc.nextInt();
		
		System.out.println(binarySearch(N, M));
		
	}
	
	public static int binarySearch(int N, int M) {
		int start = 1;
		int end = M;
		int cnt = 0;
		int mid = 0;
		
		while(start <= end) {
			mid = (start + end) / 2;
			cnt = 0;
			for(int i=1; i<=N; i++) {
				cnt += Math.min(mid / i, N);
			}
			if(cnt >= M) end = mid - 1;
			else start = mid + 1;
			
		}
		return end + 1;
	}
	
}