BinarySearch 백준 알고리즘 1300 ‘K번째 수’ 문제풀이

Problem

세준이는 NN크기의 배열을 만들었다. (배열의 방 번호는 1부터 시작한다.) 그 배열을 A라고 했을 때, 배열에 들어가는 수는 A[i][j] = ij 이다. 세준이는 이 수를 일차원 배열 B에 넣으려고 한다. 그렇게 되면, B의 크기는 N*N이 될 것이다. 그러고 난 후에, B를 오름차순 정렬해서 k번째 원소를 구하려고 한다. N이 주어졌을 때, k번째 원소를 구하는 프로그램을 작성하시오.

Input
첫째 줄에 배열의 크기 N이 주어진다. N은 105보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(109, n2)보다 작거나 같은 자연수이다.

Output
k번째 원소를 출력한다.

Solution

• K번째 수는 절대 K보다 클 수가 없다 –> high = k
• 배열의 방 번호는 1부터 시작한다 –> low = 1
• i번째 행은 i의 배수이다. –> K번째 수가 x일 때, x이하의 수는 x/i 또는 n (1번째 행의 최대값은 n이므로)

Code

import java.util.Scanner;
public class Main {
	public int solution(int n, int k) {
		int high = k, low = 1, mid = 0, sum = 0, answer = 0;
		
		while(low <= high) {
			mid = (high + low) / 2;
			sum = 0;
			for(int i = 1; i <= n; i++)
				sum += Math.min(mid / i, n);
			
			if(sum >= k) {
				high = mid - 1;
				answer = mid;
			}else
				low = mid + 1;
		}		
		return answer;
	}
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt(), k = scan.nextInt();	
		System.out.println(new Main().solution(n, k));
	}
}